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

线性表及栈数学与计算机学院课程设计说明书课 程 名 称: 数据结构与算法A设计实践 课 程 代 码: 6015059 题 目 一: 线性表的链式表示和实现 题 目 二: 利用栈实现表达式求解 年级/专业/班: 2011/信科/2班 学 生 姓 名: 彭丹 学 号: 312011070102205 开 始 时 间: 2014 年 5 月 28 日完 成 时 间: 2014 年 6 月 28 日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总 分（100）指导教师签名： 年 月 日目 录摘要11 引言22 实验一32.1整体设计思路32.2编码32.3程序演示6摘 要 随着计算机的普遍应用与日益发展，其应用早已不局限于简单的数值运算，数据结构与算法的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。数据结构与算法旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。 本次数据结构实践的第一个实验是线性表的链式表示和实现，要求动态地建立循环链表并实现循环链元素的插入，删除，查询；使用双向链的结构实现判断一个录入的字符串是否是回文；建立一个单向链表，实现其内元素非递减排序。 关键词：数据结构与算法 线性表 链式结构 栈 表达式求解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. 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 )/当icount时 在末尾添加，且规定当i=0时在末尾添加 beAdd-lpoint = p; 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/当1icount时候 int j = 1; while ( j 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, i ); return error; node *p = *head; int j = 1; while ( j lpoint; p-fpoint-lpoint = p-lpoint; 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 data != p1-data ) flag = false; break; 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：插入前后对比：查询节点值 100：以上链表排序前后对比：删除第3个节点：判断回文：结 论 这一次的课程设计相比之前的几次算是比较简单和轻松的了，但是还是会有很多问题出现，主要问题体现在对C语言的遗忘，有些东西不记得了，需要看以前的学习的书再次巩固一下。本次实践做了两个题，一个是线性表的链式表示和实现，另一个是利用栈实现表达式求解。在做线性表的时候对指针的使用还不是很好，容易出错，在同学及老师的帮助下，顺利解决。在做利用栈实现表达式求解问题的时候，对栈的理解必须到位才可以做好，特别是表达式求解时什么时候进栈什么时候出栈是很重要的，匹配括号是其中一个难点。经过本次课程设计，相当于复习了C语言和数据结构，也锻炼了程序设计的能力，收获颇多。参考文献1谭浩强 等.C语言程序设计教程.高等教育出版社.20052李建学 等.数据结构课程设计案例精编（用C/C+描述）.清华大学出版.2007-2-13严蔚敏 等.数据结构(C语言版).清华大学出版社.2003-1附录：Cpp1：函数部分#include stdafx.h#include#include #include #include #includeusing namespace System;#define false 0#define true 1#define error -1#define ok 1#define overflow -2typedef int status;typedef int elemtype;typedef struct node elemtype data; struct node *fpoint; struct node * lpoint;node; /结构体类型nodestatus creatList ( node *head )/创建链表/关于此处的*：当我们写：node*head 只是定义了一个指向node的指针，显然，此处我们还要改写这个指针head的值 ，所以我们需要指向该指针的指针node*p；父函数调用时传递一个head类型指针的地址即可：&head，否则会出现类型不匹配错误！ *head = (node *)malloc ( sizeof (node) ); (*head)-data = 100; (*head)-fpoint = *head;/*head 表示head指针实际指向的地址！ (*head)-lpoint = *head; if ( head = NULL ) exit ( overflow ); return ok;status creatNode ( node *no, elemtype elem ) *no = (node *)malloc ( sizeof (node) ); (*no)-data = elem; (*no)-fpoint = *no;/ 前指针 (*no)-lpoint = *no;/后指针 if ( no = NULL ) exit ( overflow ); return ok;int countNode ( node *head )/计算节点数 int cout; if ( head = NULL ) return 0; else cout+; node *h = head; while ( h-lpoint != head ) cout+; h = h-lpoint; return cout;status outList ( node *head ) printf ( 序号t节点值n ); if ( head != NULL ) node *h = head; node *h1 = head; int i = 1; do printf ( %4dt%6dn, i, h-data ); h = h-lpoint; i+; while ( h != head ) printf ( %4dt%6d n, i, h-data ); i+; h = h-lpoint; break; while ( h != NULL ); 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 ) beAdd-lpoint = p; beAdd-fpoint = p-fpoint; beAdd-fpoint-lpoint = beAdd; p-fpoint = beAdd; return ok; else if ( i = 1 ) beAdd-lpoint = p; beAdd-fpoint = p-fpoint; beAdd-fpoint-lpoint = beAdd; p-fpoint = beAdd; p = p-fpoint; *head = p; return ok; else int j = 1; while ( j lpoint; beAdd-lpoint = p; beAdd-fpoint = p-fpoint; beAdd-fpoint-lpoint = beAdd; p-fpoint = beAdd; return ok; status outNode ( node * head, int i ) return ok;status deleteNode ( node *head, int i ) if ( countNode ( *head ) 1 | countNode ( *head ) i ) printf ( 链表head中不包含第 %d 个节点n, i ); return error; node *p = *head; int j = 1; while ( j lpoint; p-fpoint-lpoint = p-lpoint; p-lpoint-fpoint = p-fpoint; if ( i = 1 ) if ( *head = (*head)-lpoint ) (*head) = NULL; else *head = (*head)-lpoint; free ( p ); return ok;status removeNode ( node *head, int i, node *no ) if ( countNode ( *head ) 1 | countNode ( *head ) i ) printf ( 链表head中不包含第 %d 个节点n, i ); return error; node *p = *head; int j = 1; while ( j lpoint; p-fpoint-lpoint = p-lpoint; p-lpoint-fpoint = p-fpoint; if ( i = 1 ) if ( *head = (*head)-lpoint ) (*head) = NULL; else *head = (*head)-lpoint; p-fpoint = p; p-lpoint = p; *no = p; return ok;status freeList ( node *head ) return ok;int findMin ( node *head ) node *p = head; if ( p = NULL ) puts ( 链表为空！ ); return 0; int min = p-data; while ( p != NULL&p-lpoint != head ) p = p-lpoint; if ( p-datadata; return min;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;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 ); addNode ( &newHead, 0, temp ); temp = NULL; *head = newHead; return ok;bool isHuiWen ( node *head ) bool flag = true; node *p = head; node*p1 = p-fpoint; int i = countNode ( head ) / 2; int j = 1; while ( j data != p1-data ) flag = false; break; j+; return flag;Cpp2：菜单部分：/ data_struct_design.cpp: 主项目文件。#include stdafx.h#include#include #include #include #includeusing namespace System;#define false 0#define true 1#define error -1#define ok 1#define overflow -2typedef int status;typedef int elemtype;typedef struct node elemtype data; struct node *fpoint; struct node * lpoint;node; /结构体类型nodestatus outList ( node *head );status outNode ( node * head, int i );status deleteNode ( node *head, int i );status freeList ( node *head );status sortList ( node *head );status creatList ( node *head );status creatNode ( node *no, elemtype elem );int countNode ( node *head );status addNode ( node *head, int i, node *beAdd );int findNode ( node *head, elemtype elem );status removeNode ( node *head, int i, node *no );int findMin ( node *head );bool isHuiWen ( node *head );void func1_2 ( );void menu ( ) system ( cls ); puts ( 第二题：线性表的链式表示和实现2 ); puts ( 1 动态地建立循环链表； ); puts ( 2 实现循环链元素的插入，删除，查询； ); puts ( 3 使用双向链的结构实现判断一个录入的字符串是否是回文。 ); puts ( 4 建立一个单向链表，实现其内元素非递减排序 ); puts ( * ); char a10; gets ( a ); switch ( a0 ) case 1: puts ( 1 动态地建立循环链表： ); node *head; node *p; creatList ( &head ); creatNode ( &p, 21 ); addNode ( &head, 1, p ); creatNode ( &p, 302 ); addNode ( &head, 1, p ); creatNode ( &p, 3 ); addNode ( &head, 1, p ); creatNode ( &p, 45 ); addNode ( &head, 1, p ); creatNode ( &p, 57 ); addNode ( &head, 0, p ); outList ( head ); puts ( 任意键返回： ); getche ( ); while ( countNode ( head ) != 0 ) deleteNode ( &head, countNode ( head ) ); menu ( ); break; case 2: func1_2 ( ); break; case 3: system ( cls ); char a100; puts ( 请输入要判断的字符串 ); gets ( a ); int i = 0; node *p = NULL; node *h = NULL; while ( ai != 0 ) creatNode ( &p, ai ); addNode ( &h, 0, p ); i+; if ( isHuiWen ( h ) ) puts ( 您输入的字符串是回文！ ); else puts ( 您输入的字符串不是回文！ ); puts ( 字符串的正反序对比：n正序t反序n ); int j = 0; node *m = h; node *n = h-fpoint; while ( j data, n-data ); m = m-lpoint; n = n-fpoint; j+; bool f = isHuiWen ( h ); puts ( 任意键返回 ); getche ( ); menu ( ); ; break; case 4: puts ( 4 建立一个单向链表，实现其内元素非递减排序 ); node *head; node *p; creatList ( &head ); creatNode ( &p, 21 ); addNode ( &head, 1, p ); creatNode ( &p, 302 ); addNode ( &head, 1, p ); creatNode ( &p, 3 ); addNode ( &head, 1, p ); creatNode ( &p, 45 ); addNode ( &head, 1, p ); creatNode ( &p, 57 ); addNode ( &head, 0, p ); outList ( head ); sortList ( &head ); puts ( 排序后的链表： ); outList ( head ); puts ( 任意键返回 ); getche ( ); while ( countNode ( head ) != 0 ) deleteNode ( &head, countNode ( head ) ); menu ( ); break; default: menu ( ); puts ( 输入不正确，请重新输入： ); void func1_2 ( ) system ( cls ); puts ( 2 实现循环链元素的插入，删除，查询: ); node *head; node *p; creatList ( &head ); creatNode ( &p, 21 ); addNode ( &head, 1, p ); creatNode ( &p, 302 ); addNode ( &head, 1, p ); creatNode ( &p, 3 ); addNode ( &head, 1, p ); creatNode ( &p, 45 ); addNode ( &head, 1, p ); creatNode ( &p, 57 )