《数据结构实验C语言版(1)》由会员分享，可在线阅读，更多相关《数据结构实验C语言版(1)（72页珍藏版）》请在金锄头文库上搜索。
1、南阳理工学院南阳理工学院 数据结构数据结构(C 语言版语言版)上机实验指导书上机实验指导书 软件学院软件工程 目目 录录 实验 1 线性表应用 实验 2 栈和队列的应用 14 实验 3 线性表应用 27 实验 4 图论及其应用 46 实验 5 查找 实验 6 排序 64 实验实验 1 线性表应用线性表应用 1 1、实验目的实验目的 3，了解和掌握线性表顺序存储和链式存储在计算机中的表示，基本操做在计算机中的实 2，能够利用线性表结构对实际问题进行分析建模，利用计算机求解。 1，能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。 二、实验内容及步骤二、实验内容及步骤
2、1、利用程序设计语言分别实现顺序表和链表的抽象数据类型。 2、掌握程序分文件（头文件和实现文件）书写的方式。 3、分别用顺序表和链表实现课本算法 2.2：合并两个非递减有序序列，并对其时间性能做 出分析。 三、实验步骤与调试过程三、实验步骤与调试过程 以线性表来描述一元多项式，储存结构采用单链表，每个结点储存的多项式中某一项 的系数和指数，建立单链表时指数高的结点列于指数低的结点之后，即线性表的元素按指 数递增有序排列。 四、实验结果四、实验结果 五、疑难小结五、疑难小结 当线性表的长度变化较大，难以估计其存储规模，另外对线性表频繁进行插入和删除 操作时，则采用链表作为存储结构可能会更好一些。
3、在实际应用中应该考虑以下因素：(1) 应有利于运算的实现；(2)应有利于数据的特性；(3)应有利于软件环境。 六、主要算法和程序清单六、主要算法和程序清单 顺序表的非递减数列合并 #include/*包含输入输出头文件*/ #define ListSize 100 typedef int DataType; typedef struct DataType listListSize; int length; SeqList; void InitList(SeqList *L) /*将线性表初始化为空的线性表只需要把线性表的长度 length 置为 0*/ L-length=0; /*把线性表的长
4、度置为 0*/ int ListEmpty(SeqList L) /*判断线性表是否为空，线性表为空返回 1，否则返回 0*/ if(L.length=0)/*判断线性表的长度是否为 9*/ return 1;/*当线性表为空时，返回 1；否则返回 0*/ else return 0; int GetElem(SeqList L,int i,DataType *e) /*查找线性表中第 i 个元素。查找成功将该值返回给 e，并返回 1 表示成功；否则返回-1 表 示失败。*/ if(iL.length) /*在查找第 i 个元素之前，判断该序号是否合法*/ return -1; *e=L.li
5、sti-1;/*将第 i 个元素的值赋值给 e*/ return 1; int LocateElem(SeqList L,DataType e) /*查找线性表中元素值为 e 的元素，查找成功将对应元素的序号返回，否则返回 0 表示失 败。*/ int i; for(i=0;iL-length+1)/*在插入元素前，判断插入位置是否合法*/ printf(“插入位置 i 不合法！n“); return -1; else if(L-length=ListSize)/*在插入元素前，判断顺序表是否已经满，不能插入 元素*/ printf(“顺序表已满，不能插入元素。n“); return 0; e
6、lse for(j=L-length;j=i;j-)/*将第 i 个位置以后的元素依次后移*/ L-listj=L-listj-1; L-listi-1=e;/*插入元素到第 i 个位置*/ L-length=L-length+1;/*将顺序表长增 1*/ return 1; int DeleteList(SeqList *L,int i,DataType *e) int j; if(L-lengthL-length) printf(“删除位置不合适!n“); return -1; else *e=L-listi-1; for(j=i;jlength-1;j+) L-listj-1=L-lis
7、tj; L-length=L-length-1; return 1; int ListLength(SeqList L) return L.length; void ClearList(SeqList *L) L-length=0; void MergeList(SeqList A,SeqList B,SeqList *C);/*合并顺序表 A 和 B 中元素的函数声明 */ void main() int i,flag; DataType a=6,11,11,23; DataType b=2,10,12,12,21; DataType e; SeqList A,B,C;/*声明顺序表 A，B
8、 和 C*/ InitList(/*初始化顺序表 A*/ InitList(/*初始化顺序表 B*/ InitList(/*初始化顺序表 C*/ for(i=1;ilength=A.length+B.length;/*C 的表长等于 A 和 B 的表长的和*/ 链式表的非递减数列合并链式表的非递减数列合并 /*包含头文件*/ #include #include #include /*宏定义和单链表类型定义*/ #define ListSize 100 typedef int DataType; typedef struct Node DataType data; struct Node *ne
9、xt; ListNode,*LinkList; void MergeList(LinkList A,LinkList B,LinkList *C); /*将单链表 A 和 B 的元素合并到 C 中的 函数声明*/ void InitList(LinkList *head) /*将单链表初始化为空。动态生成一个头结点，并将头结点的指 针域置为空。*/ if(*head=(LinkList)malloc(sizeof(ListNode) =NULL)/*为头结点分配一个存储空间*/ exit(-1); (*head)-next=NULL; /*将单链表的头结点指针域置为空*/ int ListEm
10、pty(LinkList head) /*判断单链表是否为空，就是通过判断头结点的指针域是否为空 */ if(head-next=NULL)/*判断 单链表头结点的指针域是否为空*/ return 1; /*当单链表为空时，返回 1；否则返回 0*/ else return 0; ListNode *Get(LinkList head,int i) /*查找单链表中第 i 个结点。查找成功返回该结点的指针表示成 功；否则返回 NULL 表示失败。*/ ListNode *p; int j; if(ListEmpty(head)/*在查找第 i 个元素之前， 判断链表是否为空*/ return
11、NULL; if(inext!=NULL j+; if(j=i) return p;/*找到第 i 个结点 ，返回指针 p*/ else return NULL ;/*如果没有找到第 i 个元 素，返回 NULL*/ ListNode *LocateElem(LinkList head,DataType e) /*查找线性表中元素值为 e 的元素，查找成功将对应元素的结点 指针返回，否则返回 NULL 表示失败。*/ ListNode *p; p=head-next;/*指针 p 指向第一个结点*/ while(p) if(p-data!=e) /*找到与 e 相等的元素，返 回该序号*/ p
12、=p-next; else break; return p; int LocatePos(LinkList head,DataType e) /*查找线性表中元素值为 e 的元素，查找成功将对应元素的序号 返回，否则返回 0 表示失败。*/ ListNode *p; int i; if(ListEmpty(head)/*在查找第 i 个元 素之前，判断链表是否为空*/ return 0; p=head-next;/*指针 p 指向第一 个结点*/ i=1; while(p) if(p-data=e)/*找到与 e 相等的 元素，返回该序号*/ return i; else p=p-next;
13、i+; if(!p)/*如果 没有找到与 e 相等的元素，返回 0，表示失败*/ return 0; int InsertList(LinkList head,int i,DataType e) /*在单链表中第 i 个位置插入一个结点，结点的元素值为 e。插入 成功返回 1，失败返回 0*/ ListNode *p,*pre; /*定义指向第 i 个元素的前 驱结点指针 pre，指针 p 指向新生成的结点*/ int j; pre=head;/*指针 p 指向头结 点*/ j=0; while(pre-next!=NULL j+; if(!pre) /*如果没找到，说明插入位置错误*/ pr
14、intf(“插入位置错“); return 0; /*新生成一个结点，并将 e 赋值给该结点的数据域*/ if(p=(ListNode*)malloc(sizeof(ListNode)=NULL) exit(-1); p-data=e; /*插入结点操作*/ p-next=pre-next; pre-next=p; return 1; int DeleteList(LinkList head,int i,DataType *e) /*删除单链表中的第 i 个位置的结点。删除成功返回 1，失败返回 0*/ ListNode *pre,*p; int j; pre=head; j=0; while
15、(pre-next!=NULL j+; if(j!=i-1)/*如果没找到要 删除的结点位置，说明删除位置错误*/ printf(“删除位置错误“); return 0; /*指针 p 指向单链表中的第 i 个结点，并将该结点的数据 域值赋值给 e*/ p=pre-next; *e=p-data; /*将前驱结点的指针域指向要删除结点的下一个结点， 也就是将 p 指向的结点与单链表断开*/ pre-next=p-next; free(p);/*释放 p 指向的结 点*/ return 1; int ListLength(LinkList head) ListNode *p; int count
16、=0; p=head; while(p-next!=NULL) p=p-next; count+; return count; void DestroyList(LinkList head) ListNode *p,*q; p=head; while(p!=NULL) q=p; p=p-next; free(q); void main() int i; DataType a=6,7,9,14,37,45,65,67; DataType b=3,7,11,34,45,89; LinkList A,B,C;/*声明单链表 A 和 B*/ ListNode *p; InitList(/*初始化单链表
