C语言 - 双向循环链表、增删查改、判断回文、排序、论文+代码

数学与计算机学院 课程设计说明书

课 程 名 称: 数据结构与算法A设计实践 课 程 代 码: 6015059 题 目 一: 线性表的链式表示和实现 题 目 二: 利用栈实现表达式求解 年级/专业/班: 2011/信科/2班 学 生 姓 名: XXX 学 号: XXX

开 始 时 间: 2014 年 5 月 28 日 完 成 时 间: 2014 年 6 月 28 日 课程设计成绩：

学习态度及平技术水平与实际时成绩（30） 能力（20） 创新（5） 说明书撰写质量（45） 总 分（100） 指导教师签名： 年 月 日

目 录

摘要………………………………………………………………………………1 1 引言……………………………………………………………………………2 2 实验一…………………………………………………………………………3 2.1整体设计思路………………………………………………………………3 2.2编码…………………………………………………………………………3 2.3程序演示……………………………………………………………………6

摘 要

随着计算机的普遍应用与日益发展，其应用早已不局限于简单的数值运算，数据结

构与算法的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。数据结构与算法旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。

本次数据结构实践的第一个实验是线性表的链式表示和实现，要求动态地建立循环链表并实现循环链元素的插入，删除，查询；使用双向链的结构实现判断一个录入的字符串是否是回文；建立一个单向链表，实现其内元素非递减排序。

关键词：数据结构与算法 线性表 链式结构 栈 表达式求解

1

线性表及栈

1 引 言

1. 1问题的提出

数据结构课程设计是重要地实践性教学环节。在进行了程序设计语言课和 《数据结构与算法》课程教学的基础上，设计实现相关的数据结构经典问题，有助于加深对数据结构课程的认识。本课程设计是数据结构中的一个关于线性表链式表示的实现还有用栈实现表达式求解，此课程设计要求对栈存储结构和链表存储结构非常熟悉，并能熟练使用它们。

1.2 C语言

C语言既有高级语言的特点，又具有汇编语言的特点；既是一个成功的系统设计语言，有时一个使用的程序设计语言；既能用来编写不依赖计算机硬件的应用程序，又能用来编写各种系统程序；是一种受欢迎、应用广泛的程序设计语言。

1.3 C语言发展过程

1973年，美国贝尔实验室的D.M.RITCHIE在B语言的基础上最终设计出了一种新的语言，他取了BCPL的第二个字母作为这种语言的名字，这就是C语言。

1977年Dennis M.Ritchie 发表了不依赖于具体机器系统的C语言编译文本《可移植的C语言编译程序》。

1978年Brian W.Kernighian和Dennis M.Ritchie出版了名著《The C Programming Language》，从而使C语言成为目前世界上流行最广泛的高级程序设计语言。

1.4任务

题目一：线性表的链式表示和实现

第一个实验主要是实现一些线性表的基本操作。包括（1）动态地建立循环链表；（2）实现循环链元素的插入，删除，查询；（3）使用双向链的结构实现判断一个录入的字符串是否是回文；（4）建立一个单向链表，实现其内元素非递减排序。

2

线性表及栈

2 实验一 线性表的链式表示和实现

2. 1整体设计思路

1、实现循环链表建立要定义链表的节点，一个节点至少应该包含数据域（data），指针域（point）两个部分，动态建立循环链表的过程实际上就是生成节点并且将节点一个个相连接的过程。

2、链元素的增删查；增加节点既在指定的序号处添加节点的操作；删除既从链表中取掉某个节点；查询既匹配某个值，返回节点位置的操作。

3、回文是从首到尾读自负与从尾到首读取字符都一样的字符串，我们将字符串的每个字符分别存入一个节点中，饭后将节点连接起来就构成了一个字符串链表。我们取第一个和最后一个节点，然后比较他们的值（data）是否相等，若相等则取第二个和倒数第二个比较……以此类推直到娶到最中间的字符为止，由此便可判断出字符串是否回文。

4、排序：由于要递增排序，我们先在被排序的链表中选出最小的值得节点，然后将节点从链表中移除，再将这个节点添加到一个新建的链表，然后以此选择最小值添加到该链表的末尾，当原链表不含任何元素时，新链表即为排好序的链表。

2.2 编码：

创建节点：

status creatNode ( node **no, elemtype elem )//创建节点 {

*no = (node *)malloc ( sizeof (node) ); (*no)->data = elem;

(*no)->fpoint = *no;//*head 表示head指针实际指向的地址 (*no)->lpoint = *no; if ( no == NULL ) exit ( overflow ); return ok; }

增加节点：

status addNode ( node **head, int i, node *beAdd )//增加节点 {

if ( *head == NULL ) {

*head = beAdd; return ok; }

node *p = *head;

int count = countNode ( p );

if ( i > countNode ( p ) || i == 0 )//当i>count时 在末尾添加，且规定当i==0时在末尾添加

{

beAdd->lpoint = p;

3

线性表及栈

beAdd->fpoint = p->fpoint;

beAdd->fpoint->lpoint = beAdd; p->fpoint = beAdd; return ok; }

else if ( i == 1 )//当i=1的时候 {

beAdd->lpoint = p;

beAdd->fpoint = p->fpoint;

beAdd->fpoint->lpoint = beAdd; p->fpoint = beAdd; p = p->fpoint; *head = p; return ok; }

else//当1

int j = 1; while ( j < i ) {

j++;

p = p->lpoint; }

beAdd->lpoint = p;

beAdd->fpoint = p->fpoint;

beAdd->fpoint->lpoint = beAdd; p->fpoint = beAdd; return ok; } }

删除节点：

status deleteNode ( node **head, int i )//删除节点 {

if ( countNode ( *head ) < 1 || countNode ( *head ) < i ) {

printf ( \链表head中不包含第 %d 个节点\\n\ return error; }

node *p = *head; int j = 1; while ( j < i ) {

j++;

p = p->lpoint; }

p->fpoint->lpoint = p->lpoint;

4

线性表及栈

p->lpoint->fpoint = p->fpoint; if ( i == 1 )

if ( *head == (*head)->lpoint ) (*head) = NULL; else

*head = (*head)->lpoint; free ( p ); return ok; }

查询节点：

int findNode ( node *head, elemtype elem )//根据值找到节点 {

int pos = 0; node *p = head; pos++;

if ( p == NULL ) return 0;

else if ( p->data == elem ) return pos;

while ( p != NULL&&p->lpoint != head ) {

p = p->lpoint; pos++;

if ( p->data == elem ) {

return pos; break; } }

return 0; }

判断回文：

bool isPalin ( node *head )//判断回文 {

bool flag = true;//标志量 true表示是回文 node *p = head;

node*p1 = p->fpoint;

int i = countNode ( head ) / 2; int j = 1;

while ( j <= i ) {

if ( p->data != p1->data ) {

flag = false; break; }

5

线性表及栈

j++; }

return flag; }

链表排序：

status sortList ( node **head )// 排序 {

int minPos;//最小节点的位置 node *h = *head;

node *newHead = NULL;//新建的链表 node *temp = NULL;

while ( countNode ( h ) != 0 )//当原链表不为空 {

removeNode ( &h, findNode ( h, findMin ( h ) ), &temp );//将找到的最小节点从原链表中移除，并放入temp节点中

addNode ( &newHead, 0, temp );//将temp节点插入新链表的末尾 temp = NULL; }

*head = newHead; return ok; }

2.3 程序演示：

程序开始：

输入2 选择增、删、查项。插入一个节点在第二个节点前，值为203：

6

线性表及栈

插入前后对比：

查询节点值 100：

7

线性表及栈

以上链表排序前后对比：

删除第3个节点：

8

本文来源：https://www.bwwdw.com/article/varp.html