软件英才网软件行业驰名招聘网站
一步一步写算法（之循环单向链表）
前面的博客中，我们曾经有一篇专门讲到单向链表的内容。那么今天讨论的链表和上次讨论的链表有什么不同呢？重点就在这个"循环"上面。有了循环，意味着我们可以从任何一个链表节点开始工作，可以把root定在任何链表节点上面，可以从任意一个链表节点访问数据，这就是循环的优势。
那么在实现过程中，循环单向链表有什么不同？
1）打印链表数据
1void print_data(const LINK_NODE* pLinkNode)
2{
3 LINK_NODE* pIndex = NULL;
4if(NULL == pLinkNode)
5return;
6
7 printf("%d\n", pLinkNode->data);
8 pIndex = pLinkNode->next;
9while(pLinkNode != pIndex){
10 printf("%d\n", pIndex->data);
11 pIndex = pIndex ->next;
12 }
13}
以往，我们发现打印数据的结束都是判断指针是否为NULL，这里因为是循环链表所以发生了变化。原来的条件（NULL != pLinkNode）也修改成了这里的（pLinkNode != pIndex）。同样需要修改的函数还有find函数、count统计函数。
2）插入数据
14STATUS insert_data(LINK_NODE** ppLinkNode, int data)
15{
16 LINK_NODE* pNode;
17if(NULL == ppLinkNode)
18return FALSE;
19
20if(NULL == *ppLinkNode){
21 pNode = create_link_node(data);
22 assert(NULL != pNode);
软件英才网软件行业驰名招聘网站23
24 pNode->next = pNode;
25 *ppLinkNode = pNode;
26return TRUE;
27 }
28
29if(NULL != find_data(*ppLinkNode, data))
30return FALSE;
31
32 pNode = create_link_node(data);
33 assert(NULL != pNode);
34
35 pNode->next = (*ppLinkNode)->next;
36 (*ppLinkNode)->next = pNode;
37return TRUE;
38}
这里的insert函数在两个地方发生了变化：a）如果原来链表中没有节点，那么链表节点需要自己指向自己
b）如果链表节点原来存在，那么只需要在当前的链表节点后面添加一个数据，同时修改两个方向的指针即可
3）删除数据
39STATUS delete_data(LINK_NODE** ppLinkNode, int data)
40{
41 LINK_NODE* pIndex = NULL;
42 LINK_NODE* prev = NULL;
43if(NULL == ppLinkNode || NULL == *ppLinkNode)
44return FALSE;
45
46 pIndex = find_data(*ppLinkNode, data);
47if(NULL == pIndex)
48return FALSE;
49
50if(pIndex == *ppLinkNode){
51if(pIndex == pIndex->next){
52 *ppLinkNode = NULL;
53 }else{
54 prev = pIndex->next;
软件英才网软件行业驰名招聘网站55while(pIndex != prev->next)
56 prev = prev->next;
57
58 prev->next = pIndex->next;
59 *ppLinkNode = pIndex->next;
60 }
61 }else{
62 prev = pIndex->next;
63while(pIndex != prev->next)
64 prev = prev->next;
65 prev->next = pIndex->next;
66 }
67
68 free(pIndex);
69return TRUE;
70}
和添加数据一样，删除数据也要在两个方面做出改变：a）如果当前链表节点中只剩下一个数据的时候，删除后需要设置为NULL
b）删除数据的时候首先需要当前数据的前一个数据，这个时候就可以从当前删除的数据开始进行遍历
c）删除的时候需要重点判断删除的数据是不是链表的头结点数据
1
历年链表考题及答案 [2005秋II.14] 设已建立了两条单向链表，这两链表中的数据已按从小到大的次序排好，指针h1和h2分别指向这两条链表的首结点。链表上结点的数据结构如下： struct node{ int data; node *next; }; 以下函数node *Merge(node *h1, node *h2)的功能是将h1和h2指向的两条链表上的结点合并为一条链表，使得合并后的新链表上的数据仍然按升序排列，并返回新链表的首结点指针。 算法提示：首先，使newHead和q都指向首结点数据较小链表的首结点，p指向另一链表首结点。其次，合并p和q所指向的两条链表。在q不是指向链尾结点的情况下，如果q 的下一个结点数据小于p指向的结点数据，则q指向下一个结点；否则使p1指向q的下一个结点，将p指向的链表接到q所指向的结点之后，使q指向p所指向的结点，使p指向p1所指向的链表。直到p和q所指向的两条链表合并结束为止。注意，在合并链表的过程中，始终只有两条链表。 [函数] （4分） node * Merge(node *h1, node *h2) { node *newHead, *p, *p1; // 使newHead和q指向首结点数据较小链表的首结点，p指向另一链表首结点if( (27) ) { newHead=h1; p=h2; } // h1->data
算法案例 知识讲解 一、更相减损术 1.概念：求两个整数的最大公约数的算法. 2.步骤：以两个数中较大的数减去较小的数，以差数和较小的数构成一对新的数，对这一对数再用大数减小数，以同样的操作一直做下去，直到产生一对相等的数，此数就是这两个数的最大公约数． 3.等值算法：用“更相减损术”设计出来的算法求最大公约数的算法称为“等值算法”，用等值算法可以求任意两个正整数的最大公约数． 4.原理：《九章算法》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数．以具体的例子来说明更相减损术求最大公约数的原理：以求117和182的最大公约数为例：(117182)(11765)(6552)(5213)(1339)(1326)(1313)，，，，，，，， →→→→→→ 每次操作后得到的两个数与前两个数的最大公约数相同，而且逐渐减少，故总能得到相等的两个数，即为所求的最大公约数． 二、辗转相除法 1.概念：辗转相除法又称欧几里得算法，是由欧几里得在公元前300年左右首先提出来的求两个数的最大公约数的算法． 2.步骤：对于给定的两个数，以其中较大的数除以较小的数得到一个余数，将较小的数与余数看成一对新的数，重复上面的步骤，直到余数为零为止，此时上一步中较小的数即为所求的最大公约数． 如：(117182)(11765)(6552)(5213)(130) ，，，，，,故13即为所求． →→→→ 三、秦九韶算法 1.用途：秦九韶算法求多项式的值 2.具体内容：已知一个多项式函数，计算多项式在某点处的函数值的一种算法，是我国古
代数学家秦九韶提出的，具体如下： 对任意一个n 元多项式1110()n n n n f x a x a x a x a --=++++， 改写成如下形式：12110()()n n n n f x a x a x a x a ---=++ ++ 231210(())n n n n a x a x a x a x a ---=++ +++ = 1210((()))n n n a x a x a x a x a --=+++++， 求多项式的值时，先计算最内层括号内的一次多项式的值，即11n n v a x a -=+， 然后由内向外逐层计算一次多项式的值， 即212n v v x a -=+，323n v v x a -=+， ，10n n v v x a -=+． 这样，求一个n 次多项式的值，就转化为求n 个一次多项式的值． 令1(1)(())k n n n k n k v a x a x a x a ----=++++，则递推公式为01n k k n k v a v v x a --=??=+?, 其中12k n =，，，． 到目前为止，此算法仍然是世界上多项式求值的最先进的算法． 3.秦九韶算法与其它算法的比较：1110()n n n n f x a x a x a x a --=++ ++， （1）直接求和法：先计算各个单项式的值，再把它们相加，乘法次数为 (1) (1)212 n n n n ++-+++= ，加法次数n ； （2）逐项求和法：先计算x 的各项幂的值，再分别相乘，计算幂值需要乘法1n -次，将幂值与多项式系数k a 相乘需要乘法n 次，故共需要乘法21n -次，加法n 次． 注：此方法对直接求和法有所改进，但仍然比秦九韶算法计算量大很多． （3）秦九韶算法：计算量仅为乘法n 次，加法n 次． 4.秦九韶算法的特点： 1）化高次多项式求值为一次多项式求值； 2）减少了运算次数，提高了效率； 3）步骤重复执行，容易用计算机实现． 注意：利用秦九韶算法计算多项式的值关键是能正确地将所给多项式改写，然后由内向外逐
这个星期做数据结构课设，涉及到两个基于链表的排序算法，分别是基于链表的选择排序算法和归并排序算法。写出来跟大家一起分享一下，希望对数据结构初学朋友有所帮助，高手就直接忽视它吧。话不多说，下面就看代码吧。 [c-sharp]view plaincopy 1.node *sorted(node *sub_root) 2.{ 3.if (sub_root->next) 4. { 5. node * second_half = NULL; 6. node * first_half = sub_root; 7. node * temp = sub_root->next->next; 8.while (temp) 9. { 10. first_half = first_half->next; 11. temp = temp->next; 12.if(temp) 13. temp = temp->next; 14. } 15. second_half = first_half->next; 16. first_half->next = NULL; 17. node * lChild = sorted(sub_root); 18. node * rChild = sorted(second_half); 19.if (lChild->data < rChild->data) 20. { 21. sub_root = temp = lChild; 22. lChild = lChild->next; 23. } 24.else 25. { 26. sub_root = temp = rChild; 27. rChild = rChild->next; 28. } 29.while (lChild&&rChild) 30. { 31.if (lChild->data < rChild->data ) 32. { 33. temp->next = lChild; 34. temp = temp->next; 35. lChild = lChild->next; 36. } 37.else 38. {
《数据结构》实验报告 1、实验名称:设计循环单链表 2、实验日期: 2013-3-26 3、基本要求： 1）循环单链表的操作，包括初始化、求数据元素个数、插入、删除、取数据元素； 2）设计一个测试主函数实际运行验证所设计循环单链表的正确性。 4、测试数据： 依次输入1，2，3，4，5，6，7，8，9，10，删除5，再依次输出数据元素。 5、算法思想或算法步骤: 主函数主要是在带头结点的循环单链表中删除第i个结点，其主要思想是在循环单链表中寻找到第i-1个结点并由指针p指示，然后让指针s指向a[i]结点，并把数据元素a[i]的值赋给x，最后把a[i]结点脱链，并动态释放a[i]结点的存储空间。 6、模块划分： 1）头文件LinList.h。头文件LinList.h中包括：结点结构体定义、初始化操作、求当前数据个数、插入一个结点操作、删除一个结点操作以及取一个数据元素操作； 2）实现文件dlb.cpp。包含主函数void main(void)，其功能是测试所设计的循环单链表的正确性。
7、数据结构： 链表中的结点的结构体定义如下： typedef struct Node { DataType data; struct Node *next; }SLNode; 8、源程序： 源程序存放在两个文件中，即头文件LinList.h和实现文件dlb.cpp。//头文件LinList.h typedef struct Node { DataType data; struct Node *next; }SLNode; void ListInitiate(SLNode **head) //初始化 { *head=(SLNode *)malloc(sizeof(SLNode)); //申请头结点，由head指示其地址 (*head)->next=*head; }
实验一线性表运算的实现 班级学号姓名 一、实验预备知识 1．复习C中函数的相关内容。 2．复习如何用主函数将多个函数连在一起构成一个C完整程序。 3．复习多文件结构。 二、实验目的 1．掌握线性表的顺序和链式存储结构 2．熟练运用线性表在顺序存储方式下的初始化、创建、输出、插入和删除运算 3．熟练运用线性表在链式存储方式下的创建、输出、插入和删除运算 三、实验要求 1．编写初始化并创建线性表和输出线性表的算法。 2．编写对线性表插入和删除运算算法，要判断位置的合法性和溢出问题。 3．编写有序表的插入和删除运算算法。 4．编写一个主函数，将上面函数连在一起，构成一个完整的程序。 5．将实验源程序调试并运行，写出输入、输出结果，并对结果进行分析。 四、实验内容 顺序表实验内容： 1．给定的线性表为L=（12，25，7，42，19，38），元素由键盘输入。 2．初始化并建立顺序表。（开辟的存储空间大小为8） 3．编写顺序表输出算法。 4．依次插入3，21，15三个数，分别插入在第4，6和2位置，每插入一次都要输出一次顺序表。 5．删除第5，第3和第12个位置上的元素，每删除一个元素都要输出一次顺序表。 6．编写一个排序算法，对线性表中元素从小到大排列。 7．向有序表分别插入20和50，插入后表仍然有序。（修改开辟的存储空间大小为15） 单链表实验内容： 1．给定的线性表为L=（12，25，7，42，19，38），元素由键盘输入。 2．建立一个带表头结点的单链表（前插入法和尾插入法都可以）。 3．编写单链表输出算法。 4．依次插入3，21，15三个数，分别插入在第4，6和12位置，每插入一次都要输出一次单链表。 5．删除第5，第3和第12个位置上的元素，每删除一个元素都要输出一次单链表。 6．编写一个排序算法，对线性表中元素从小到大排列。 7．分别删除值为25和42的元素，删除后表仍然有序。 五、实验结果 给出程序清单及输入/输出结果 六、总结 1．实验过程中遇到的问题及解决方法 2．收获
/*1、CreateList( )：创建一个带头结点的空的单循环链表； 2、InsertList( )：输入一组数据，以0表示输入结束, 并依次建立各个元素结点，逐个插入到单循环链表尾 3、DeleteList( )：删除单循环链表的从第i个数据元素开始的m个数据元素,同时释放被删结点空间 4. ListPrint( ):将单向循环链表的数据元素从表头到表尾依次显示 5. DevList( )：将此单循环链表拆分成两个单循环链表，其中一个包含所有的数据元素为偶数的结点， 另一个包含所有的数据元素为奇数的结点.*/ #include
1.【201604学考】某算法的部分流程图如下图1所示，执行这部分流程后，变量x 的值是 A.0 B.1 C.2 D.3 2.【201509】对输入的2个整数a 和b ，找出其中的较大者赋给c 并输出。解决该问题的算法流程图如第2题图所示： A ． B. C. D. 3. 【201608温州模拟卷】某算法的部分流程 图如图所示，执行这部分流程后，变量x 和Flag 的值分别是： A.2，True B.3，True C.2，False D.3，False 4. 如下图所示的流程图，算法执行时， 若输入n 的值为5，则输出s 的值是 A ．10 B ．13 C ．16 D ．25 5.某算法的部分流程图如第5题 图所示。执行这部分流程后， “x ←x —2”被执行的次数为 A. 0 B. 1 C. 2 D. 3 6.随机产生10个[1，99]中的整数，依次存储到数组变量a(1)～a(10)中。实现此功能的部分算法流程图如图所示：(学了VB 对应函数后才能做) 图中空白处理框①和②处应填入的是 第1题图 第2题图 第3题图 第4题图
（A ）① i ← i + 1 （B ）① i ← i + 1 ② a(i) ← Rnd * 100 ② a(i) ← Int(Rnd * 100) （C ）① a(i) ← Int(Rnd * 100) （D ）① a(i) ← Int(Rnd * 99)+1 ② i ← i + 1 ② i ← i + 1 第6题图 第7题图 7.计算s = 1 + 3 + 5 + … + 99的部分算法流程图如图所示： 图中空白处理框①和②处应填入的是 （A ）① i ← i + 2 （B ）① i ← i + 1 ② s ← s + i ② s ← s + i （C ）① s ← s + i （D ）① s ← s + i ② i ← i + 2 ② i ← i + 1 8.有流程图如右图所示： 若输入a 的值为3，则该算法输出的结果为 （A ）-3 （B ）0 （C ）3 （D ）9 9.如图所示，流程图所表示的算法属于 （A ）枚举算法 （B ）排序算法 （C ）解析算法 （D ）对分算法 10.计算某球队平均年龄的部分算法流程图如图所示，其中：c 用来记录已输入球 第9题图
《数据结构》实践任务书学生姓名：专业班级： 指导教师： 题目: 基于链表的排序与查找 要求： （1）熟练掌握基本的数据结构； （2）熟练掌握各种算法； （3）运用高级语言编写质量高、风格好的应用程序。 主要任务: 1、系统应具备的功能： （1）建立链表 （2）基于链表的排序算法实现 （3）基于链表的查找算法实现 2、数据结构设计； 3、主要算法设计； 4、编程及上机实现； 5、撰写数据结构实践报告，包括： （1）设计题目； （2）摘要和关键字； （3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试等； （4）结束语； （5）参考文献。 时间安排：2014年-2015年第1学期第15周-第17周 15周星期五 1-4节系统设计，数据结构设计，算法设计 16周星期四 5-8节编程并上机调试 16周星期五 1-4节编程并上机调试 17周星期四 5-8节验收程序，提交数据结构实践报告书 指导教师签名：2014年11月
基于链表的排序和查找算法的设计 与实现 摘要：该程序的主要功能是对以链表为存储结构的数值型数据进行查找和排序。排序和查找是链表中的一个重要应用。本文对输入的n个整数进行内部排序，使用交换排序来实现。在本程序中应用链式存储结构，对数据进行了基本的查找和排序。 关键字：存储结构链表排序排序。 1.引言 查找是求出一个数据元素在序列中的索引或指针，将其返回，本程序返回的为指针。 排序是将一个数据元素(或记录)的任意序列，重新排列成一按关键字(或排序码)有序的序列，以便于进行数据查询。 2.需求分析 本程序是基于链表的排序和查找，所以数据的存储结构为连式存储结构。文件中记录用节点来表示，其物理位置任意，节点之间用指针相连，链表结构的有点在于排序是无需移动记录，只需修改相应记录的指针即可。 排序本程序选用交换排序。 3.数据结构设计
约瑟夫环问题单循环链表解法 Description 约瑟夫环问题；有N个人围成一个环，从第一个人开始报数，报到M的人退出环，并且由他的M值来代替原有的M值，要求输出离开环的顺序。 Input 第一行有2个数，M和N。(0 第二行有 N 个数，表示每个人的 M 值。 Output 按照样例的格式，输出所有人退出环的顺序。 Sample Input 4 6 5 4 2 3 4 2 Sample Output 4,1,2,3,6,5 Source #include"iostream" #include"cstdio" #include"cstdlib" using namespace std; typedef struct cnode{ int label; int data; struct cnode *next; }cnode; int m,n,i,value,j; cnode *p,*q;
int main( { cin>>m>>n; cnode *clist; q=(cnode *malloc(sizeof(cnode; clist=q; for(i=1;i<=n;i++ { //cin>>value; cin>>value; p=(cnode *malloc(sizeof(cnode; //p=new cnode; p->label=i; p->data=value; p->next=NULL; q->next=p; q=p; if(i==nq->next=clist->next; } p=clist; //cout< label< for(i=1;i<=n;i++ { for(j=1;j { p=p->next; } q=p->next; m=q->data;
数据结构实验报告 实验名称：实验四——链表的排序 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 [内容要求] 使用链表实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、冒泡排序 3、快速排序 4、简单选择排序 5、其他 要求： 1、测试数据分成三类：正序、逆序、随机数据 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其 中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒 （选作） 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度 编写测试main()函数测试线性表的正确性 代码要求 1、必须要有异常处理，比如删除空链表时需要抛出异常； 2、保持良好的编程的风格： 代码段与段之间要有空行和缩近 标识符名称应该与其代表的意义一致 函数名之前应该添加注释说明该函数的功能 关键代码应说明其功能 3、递归程序注意调用的过程，防止栈溢出
2. 程序分析 2.1 存储结构 [内容要求] 存储结构：双链表 2.2 关键算法分析 [内容要求] 定义类： template
#include
int i=-1; List *p,*data1,*q,*Last; data1=(List *)malloc(sizeof(List)); p=(List *)malloc(sizeof(List)); q=(List *)malloc(sizeof(List)); data1=head->next;//记住第一个数据地址 p=head->next; while(p->next!=NULL) { q=p; //q是前一个节点 p=p->next; //p是后一个节点 p->pre=q; //后一个节点的【前继指针】指向前一个节点的地址} Last=p; //p 就是【最后一个数据】的地址 data1->pre=Last; //【第一个元素】的【前继指针】指向【最后一个元素】的地址Last->next=data1; //【最后一个元素】的【后继指针】指向【第一个元素】的地址//双向链表构成 p=Last; printf("\n\n"); while(p->data!=1) { printf("%d ",p->data); p=p->pre; } printf("%d \n",p->data); }
1．实验要求 i.实验目的: 通过编程，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。 理解算法的主要思想及流程。 ii.实验内容： 使用链表实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、冒泡排序（改进型冒泡排序） 3、快速排序 4、简单选择排序 5、堆排序（小根堆） 要求： 1、测试数据分成三类：正序、逆序、随机数据 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中 关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选 作） 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度 编写测试main()函数测试线性表的正确性 iii.代码要求： 1、必须要有异常处理，比如删除空链表时需要抛出异常；
2、保持良好的编程的风格： 代码段与段之间要有空行和缩近 标识符名称应该与其代表的意义一致 函数名之前应该添加注释说明该函数的功能 关键代码应说明其功能 3、递归程序注意调用的过程，防止栈溢出 2. 程序分析 通过排序算法将单链表中的数据进行由小至大（正向排序） 2.1 存储结构 单链表存储数据： struct node { i nt data; n ode *next; }; 单链表定义如下： class LinkList { private : n ode * front; public : L inkList(int a[], int n); //构造 ~LinkList(); v oid insert(node *p, node *s); //插入 ……
List-DuLinkedList-将单向循环链表改为双向的 2.32 已知有一个单向循环链表，其每个结点中含有三个域：prior,data和next， 其中data为数据域，next为指向后继结点的指针域，prior也为指针域，但它的值为NULL。试编写算法将此单向循环链表改写为双向循环链表，即使prior成为指向前驱结点的指针域#include
各种基本排序算法思路介绍 1.冒泡排序： 冒泡排序的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复以上过程，仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换，使得第1个数不再大于第2个数)，将小数放前，大数放后，一直比较到最小数前的一对相邻数，将小数放前，大数放后，第二趟结束，在倒数第二个数中得到一个新的最小数。如此下去，直至最终完成排序。 由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。 冒泡排序法的改进 比如用冒泡排序将4、5、7、1、2、3这6个数排序。在该列中，第二趟排序结束后，数组已排好序，但计算机此时并不知道已经反排好序，计算机还需要进行一趟比较，如果这一趟比较，未发生任何数据交换，则知道已排序好，可以不再进行比较了。因而第三趟比较还需要进行，但第四、五趟比较则是不必要的。为此，我们可以考虑程序的优化。 为了标志在比较中是否进行了，设一个布尔量flag。在进行每趟比较前将flag置成true。如果在比较中发生了数据交换，则将flag置为false，在一趟比较结束后，再判断flag，如果它仍为true(表明在该趟比较中未发生一次数据交换)则结束排序，否则进行下一趟比较。 性能分析 若记录序列的初始状态为"正序"，则冒泡排序过程只需进行一趟排序，在排序过程中只需进行n-1次比较，且不移动记录；反之，若记录序列的初始状态为"逆序"，则需进行n(n-1)/2次比较和记录移动。因此冒泡排序总的时间复杂度为O(n*n)。 2.简单选择： 每一趟从待排序的数据元素中选出最小(或最大)的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
软件英才网软件行业驰名招聘网站 一步一步写算法（之循环单向链表） 前面的博客中，我们曾经有一篇专门讲到单向链表的内容。那么今天讨论的链表和上次讨论的链表有什么不同呢？重点就在这个"循环"上面。有了循环，意味着我们可以从任何一个链表节点开始工作，可以把root定在任何链表节点上面，可以从任意一个链表节点访问数据，这就是循环的优势。 那么在实现过程中，循环单向链表有什么不同？ 1）打印链表数据 1void print_data(const LINK_NODE* pLinkNode) 2{ 3 LINK_NODE* pIndex = NULL; 4if(NULL == pLinkNode) 5return; 6 7 printf("%d\n", pLinkNode->data); 8 pIndex = pLinkNode->next; 9while(pLinkNode != pIndex){ 10 printf("%d\n", pIndex->data); 11 pIndex = pIndex ->next; 12 } 13} 以往，我们发现打印数据的结束都是判断指针是否为NULL，这里因为是循环链表所以发生了变化。原来的条件（NULL != pLinkNode）也修改成了这里的（pLinkNode != pIndex）。同样需要修改的函数还有find函数、count统计函数。 2）插入数据 14STATUS insert_data(LINK_NODE** ppLinkNode, int data) 15{ 16 LINK_NODE* pNode; 17if(NULL == ppLinkNode) 18return FALSE; 19 20if(NULL == *ppLinkNode){ 21 pNode = create_link_node(data); 22 assert(NULL != pNode);
数据结构 实 验 报 告 实验名称：实验三排序 学生姓名： 班级： 班内序号：15 学号： 日期：2016.12.19
1．实验要求 题目2 使用链表实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、冒泡排序 3、快速排序 4、简单选择排序 5、其他 要求： 1、测试数据分成三类：正序、逆序、随机数据 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动 次数（其中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精 确到微秒（选作） 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度 编写测试main()函数测试线性表的正确性 2. 程序分析 2.1 存储结构 我使用了线性表的链式存储结构，通过建立双向循环链表进行顺序存取。每个节点分为data、next、previor。data域称为数据域，数据通过node结构存储待排序的信息；next为指针域，用来储存直接后继的地址；prior为指针域，用来储存直接前继的地址； struct Node { int data; struct Node*next; struct Node*previor; };
2.2 程序流程(或程序结构、或类关系图等表明程序构成的内容，一般为流程 { private: Node* partion(Node*first,Node*end); //快速排序一趟 public: Node*front; int comparision; //比较次数 int movement; //移动次数 LinkList() //无参构造 { front = new Node; front->next = NULL; front->previor = NULL; comparision = movement = 0; } LinkList(int a[],int n); //构造函数:建立双向链表
基于链表的排序与查找 摘要：链表是程序设计中的一种重要的动态数据结构，它是动态地进行存储分配的一种结构。链表即采用链式存储结构的线性表。对线性表，我们主要对其的操作有：建立，插入，删除，查找，排序等。此次实践主要是针对于链表的排序和查找进行。 关键字：链表排序查找 1引言 排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列，以便于进行数据的查询。而基于链表的查找是采用的动态查找表，是求出一个数据元素在序列中的索引或指针，将其返回。 2需求分析 （1）建立链表； （2）基于链表的排序算法实现； （3）基于链表的查找算法实现。 3数据结构 3.1建立链表 3.1.1节点定义 typedef struct node//定义节点 { int data; struct node *next; }lnode, *linklist; 3.1.2链表尾部插入 void insertlist(linklist l,int i)//链表尾部插入 { linklist p,s;
s=(linklist)malloc(sizeof(lnode)); s->data=i; s->next=NULL; p->next=s; } 此时，相应的主函数中应该有存储代码，才能完成数据的链式存储。 int i,n,f,a[100]; h=(lnode)malloc(sizeof(lnode)); lnode *r,*p,*s; h->data=0; h->next =NULL; r=h; printf("请输入数据的数目："); scanf("%d",&n); for(i=0;i
在链表上进行直接选择排序算法的C++描述如下: template
单循环链表基本操作 /* (程序名) */ #include