数据结构顺序表及单链表基本操作.doc

实验一 顺序表和单链表的基本操作一、 实验目的a) 掌握线性顺序存储结构的形式与特点；b) 熟练利用顺序存储结构实现线性表的基本操作；c) 熟练掌握顺序存储结构中的算法实现；d) 掌握线性表链式存储结构的特点；e) 熟练利用链式存储结构实现线性表的基本操作；f) 熟练掌握链式存储结构中的算法实现。二、 知识准备a) 线性表顺序结构的表示；b) 顺序表的基本操作：顺序表的建立、查找、插入、删除；c) 线性表链式存储结构的表示；d) 链式表的基本操作：链式表的建立、查找、插入、删除；链式存储结构表不能随机存取，只能设置一个指针变量，从表头逐步向后移动来实现插入或删除数据的位置，找到后再进行具体操作。三、 实验内容1、 下面提供的程序实现的是：设有两个按元素值递增有序的顺序表la和lb，编写程序将la表和lb表归并成一个新的递增有序的顺序表lc（值相同的元素均保留在lc表中）。*/# include datastru.h# include void merge_sqlist(SEQUENLIST la,SEQUENLIST lb,SEQUENLIST *lc)/*两有序表合并*/ int i , j , k ; i = j = k = 1 ; while( _i=la.last & j=lb.last_)/la没有到达链表尾部并且lb也没有到达链表尾部 if( la.datasi datask=la.datasi_ ;/就把la的数据放到lc中；注意lc是地址变量 k+ ; i+ ; else _lc-datask=lb.datasj_; /否则就把lb的数据放到lc中 k+ ; j+ ; while( _idatask=la.datasi _ ; /就把剩余的la数据放到lc后面 k+ ; i+; while( _ jdatask=lb.datasj_ ; /就把剩余的lb数据放到lc后面 k+;j+; lc-last =la.last+lb.last;return;main( ) SEQUENLIST la, lb, lc; int i, k, m;printf(请输入la顺序表元素，元素为整型量，用空格分开，-99为结束标志 ：);la.last = 0; i = 0; scanf(%d,&i);while (i != -99) /*输入la顺序表元素，建立有序表*/k = la.last;while(k=1) & ( i= k+1; m-) la.datasm + 1 = la.datasm;la.datask + 1 = i; la.last+;scanf(%d,&i);printf(nn请输入lb顺序表元素，元素为整型量，用空格分开，-99为结束标志 ：);lb.last = 0; i = 0; scanf(%d,&i);while (i != -99) /*输入lb顺序表元素，建立有序表*/k = lb.last;while(k=1) & ( i= k+1; m-) lb.datasm + 1 = lb.datasm;lb.datask + 1 = i; lb.last+;scanf(%d,&i); printf(nla有序表元素列表 ：);for (i = 1; i = la.last; i+) printf(% d,la.datasi);printf(n);printf(nlb有序表元素列表 ：);for (i = 1; i = lb.last; i+) printf(% d,lb.datasi);printf(n);merge_sqlist (la, lb, &lc);printf(n合并后lc有序表元素列表 ：);for (i = 1; i = lc.last; i+) printf( %d,lc.datasi);printf(n);在做的过程中我所遇到的问题： 发现头文件【# include datastru.h】无法被系统识别？在同学的帮助下得出答案：需要将目标程序“另存为”存储为【*.cpp】格式的文件。2、设L为带头结点的单链表，表中元素值无序，编写程序删除表中值相同的多余元素。*/#include datastru.h#include #include void delete1(LINKLIST *a)LINKLIST *la, *p, *q;la = a-next; /把a的第1个元素while(la != NULL) q = la; /q指向lap = q-next; / p指向la的下一个节点 while(p != NULL) if (p-data=la-data) /如果p指向的数据和la指向的数据一致 p = p-next; /p指向下一个节点q-next = p; /q的下一个节点为p,这两条语句即为删除p else p = p-next; q = q-next;/否则，p,q指针都往后走 la = la-next; int count_head(LINKLIST *head)/*带头结点的单链表: 输出单链表元素值并计数*/ int i = 0; LINKLIST *p; p = head-next; printf(输出单链表元素值 : ); while(p != NULL) i+; printf( %c,p-data); p = p-next; printf(n); return i;LINKLIST *creatlink_head_rail(LINKLIST *head)/*用尾插入法建立带头结点的单链表*/ LINKLIST *last, *t; char ch; t = (LINKLIST *)malloc(sizeof(LINKLIST); head = t; last = t; t-next = NULL; printf(单链表元素值为单个字符, 连续输入，$为结束字符 : ); while (ch = getchar() != $) t = (LINKLIST *)malloc(sizeof(LINKLIST); t-data = ch; t-next = NULL; last-next = t; last = t; return (head);main() LINKLIST *head = NULL; int num;printf(n 建立单链表nn);head = creatlink_head_rail(head);fflush(stdin);num = count_head(head);printf(n 删除重复元素后nn);delete1(head);num = count_head(head);选做：3、程序lb1.2.c实现的是建立含有若干个学生信息（包括学号、姓名、成绩）的链式存储结构表。我们实现：对链式存储结构线性表实现查找、插入、删除和逆置操作，并将结果在屏幕上输出。