数据结构--线性表

《数据结构--线性表》由会员分享，可在线阅读，更多相关《数据结构--线性表（16页珍藏版）》请在装配图网上搜索。

1、江南大学物联网工程学院上机报告课程名称 数据结构 上机名称 实验一 上机日期 2013- 1-24 班 级 计科1203 姓 名 汪俊 学号 1030412314上机报告要求 1上机名称 2上机要求 3上机环境 4程序清单(写明运行结果) 5上机体会 1. 上机名称 实验1 线性表及其运算2. 上机要求 按要求编写实验程序，将实验程序上机调试运行，输入测试数据，并给出输出的结果，最后，提交实验报告，写出调试运行的体会3. 上机环境 Visual C+ 6.04. 程序清单(写明运行结果)一、1、编写程序实现顺序表的基本操作#include#include#define MaxSize 50ty

2、pedef char ElemType;typedef structElemType dataMaxSize;int length;SeqList;/建立顺序表void CreateList(SeqList &L,ElemType a,int n)int i;for (i=0;in;i+)L.datai=ai;L.length=n;/初始化顺序表void InitList(SeqList &L)L.length=0;/置空表int ListEmpty(SeqList L)return(L.length=0);/求顺序表的长度int ListLength(SeqList L)return(L.l

3、ength);/输出顺序表的所有元素void DispList(SeqList L)int i;if(ListEmpty(L) return;for (i=0;iL.length;i+)printf(%c ,L.datai);printf(n);/取序表位置i的元素值int GetElem (SeqList L,int i, ElemType &e)if(iL.length)return 0;e=L.datai-1;return 1;/在顺序表中查找值为e的元素的位置int LocateElem(SeqList L,ElemType e)int i=0;while(i=L.length)ret

4、urn 0;elsereturn i+1;/向顺序表中插入一个元素int ListInsert(SeqList &L,int i,ElemType e)int j;if (iL.length+1)return 0;i-;for (j=L.length;ji;j-)L.dataj=L.dataj-1;L.datai=e;L.length+;return 1;/从顺序表中删除一个元素int ListDelete(SeqList &L,int i,ElemType &e)int j;if (iL.length)return 0;i-;e=L.datai;for (j=i;jL.length-1;j+

5、)L.dataj=L.dataj+1;L.length-;return 1;void main()ElemType ch,CH=a,b,c,d,e;SeqList L;InitList(L);if (ListEmpty(L)printf(顺序表为空！n);printf(创建顺序表!n);CreateList(L,CH,5);printf(输出顺序表的所有元素！n);DispList(L);printf(输出顺序表长度！n);printf(ListLength(L)=%dn,ListLength(L);printf(判断顺序表是否为空！n);printf(ListEmpty(L)=%dn,Lis

6、tEmpty(L);printf(输出顺序表的第3个元素到ch！n);GetElem(L,3,ch);printf(ch=%cn,ch);printf(输出顺序表元素a的位置！n);printf(LocateElem(L,a)=%dn,LocateElem(L,a);printf(在顺序表第4个位置插入x！); ListInsert(L,4,x);printf(输出顺序表所有元素！n);DispList(L);printf(删除顺序表第3个位置的元素！n);ListDelete(L,3,ch);DispList(L);2、 建立一个单链表，显示链表中每个节点的数据，并做删除和插入处理#incl

7、ude#include#define LEN sizeof(LinkList)typedef int ElemType;typedef struct LNode ElemType data;struct LNode *next; LinkList;void CreateListR(LinkList *&L,int n)LinkList *s,*r;int i;L=(LinkList *)malloc(sizeof(LinkList); L-next=NULL;r=L; for(i=0;idata);r-next=s; r=s;r-next=NULL; void DispList(LinkLis

8、t *L)LinkList *p=L-next;while (p!=NULL)printf(%d ,p-data);p=p-next;printf(n);void Delete(LinkList* &L,int x)LinkList *p,*q;if(L=NULL)printf(链表下溢!n);if(L-data=x) p=L;L=L-next;free(p);elseq=L; p=L-next;while(p!=NULL & p-data!=x)q=p; p=p-next;if(p!=NULL) q-next=p-next;free(p);elseprintf(未找到！n);void Ins

9、ert(LinkList* &L,int i,int x)LinkList *s,*p;int j;s=(LinkList*)malloc(sizeof(LNode);s-data=x;if(i=0) s-next=L-next;L=s;elsep=L;j=1;while(p!=NULL & jnext;if(p!=NULL) s-next=p-next;p-next=s;elseprintf(没有对应位置！n);void main()LinkList *L;int i,x,n;printf(请输入要建立的链表节点个数：n);scanf(%d,&n);CreateListR(L,n); Dis

10、pList(L); printf(请输入要删除的节点的值：n);scanf(%d,&x); Delete(L,x); DispList(L); printf(请输入要插入的节点的位置与值：);scanf(%d %d,&i,&x); Insert(L,i,x); DispList(L); 二、3、有序顺序表的合并#include#include#define MaxSize 50typedef char ElemType;typedef structElemType dataMaxSize;int length;SeqList;void CreateList(SeqList &L,ElemTyp

11、e a,int n)int i;for (i=0;in;i+)L.datai=ai;L.length=n;void InitList(SeqList &L)L.length=0;int ListEmpty(SeqList L)return(L.length=0);void DispList(SeqList L)int i;if(ListEmpty(L) return;for (i=0;iMaxSize)printf(lc的空间不够！n);return 0;i=j=k=0;while (i=la.length & j=lb.length)if (la.datai=lb.dataj)lc.data

12、k+=la.datai+;elselc.datak+=lb.dataj+;while (i=la.length)lc.datak+=la.datai+;while (i=lb.length)lc.datak+=lb.dataj+;lc.length=k-1;return 1;void main()ElemType CH1=a,c,e,g,h,CH2=b,c,f,i,j;SeqList la,lb,lc;InitList(la);printf(创建顺序表la!n);CreateList(la,CH1,5);printf(输出顺序表la的所有元素！n);DispList(la);InitList(

13、lb);printf(创建顺序表lb!n);CreateList(lb,CH2,5);printf(输出顺序表lb的所有元素！n);DispList(lb);MergeQL( la, lb,lc);/调用函数MergeQL合并表printf(输出顺序表lc的所有元素！n);DispList(lc);4、 构造两个带有头结点的有序链表la、lb，编写程序实现将la、lb合并成一个有序单链表lc#include#include#define LEN sizeof(LinkList)typedef int ElemType;typedef struct LNode /定义单链表节点类型ElemTyp

14、e data;struct LNode *next; LinkList;void CreateListR(LinkList *&L,int n)LinkList *s,*r;int i;L=(LinkList *)malloc(sizeof(LinkList); L-next=NULL;r=L; for(i=0;idata);r-next=s; r=s;r-next=NULL; /输出链表的所有元素void DispList(LinkList *L)LinkList *p=L-next;while (p!=NULL)printf(%d ,p-data);p=p-next;printf(n);/

15、对两个链表进行合并void MergeLL(LinkList *La,LinkList *Lb,LinkList *&Lc)LinkList *pa,*pb,*pc;Lc=(LinkList *)malloc(sizeof(LinkList);Lc-next=NULL;pc=Lc;pa=La-next;pb=Lb-next;while(pa!=NULL & pb!=NULL)if(pa-datadata)pc-next=pa;pa=pa-next;pc=pc-next;elsepc-next=pb;pb=pb-next;pc=pc-next;/*处理剩余部分*/if(pa!=NULL)pc-n

16、ext=pa;elsepc-next=pb;void main()LinkList *L,*P,*Q;int x,n;printf(n注意输入的数据必须为有序的！nn);printf(请输入要建立的链表L节点个数：n);scanf(%d,&n);CreateListR(L,n);/建立链表，返回头指针printf(单链表Q的结果是：n);DispList(L);/输出全部节点printf(请输入要建立的链表P节点个数：n);scanf(%d,&x);CreateListR(P,x);printf(单链表Q的结果是：n);DispList(P);/输出全部节点MergeLL(L,P,Q);/单链

17、表的合并printf(单链表Q的结果是：n);DispList(Q);/输出全部节点三、 关于约瑟夫环问题#include #include typedef struct _RingNode int pos; struct _RingNode *next; RingNode, *RingNodePtr; void CreateRing(RingNodePtr pHead, int count) RingNodePtr pCurr = NULL, pPrev = NULL; int i = 1; pPrev = pHead; while(-count 0) pCurr = (RingNodePt

18、r)malloc(sizeof(RingNode); i+; pCurr-pos = i; pPrev-next = pCurr; pPrev = pCurr; pCurr-next = pHead; void PrintRing(RingNodePtr pHead) RingNodePtr pCurr; printf(%d, pHead-pos); pCurr = pHead-next; while(pCurr != NULL) if(pCurr-pos = 1) break; printf(t%d, pCurr-pos); pCurr = pCurr-next; void KickFrom

19、Ring(RingNodePtr pHead, int m) RingNodePtr pCurr, pPrev; int i = 1; pCurr = pPrev = pHead; while(pCurr != NULL) if (i = m) printf(t%d, pCurr-pos); pPrev-next = pCurr-next; free(pCurr); pCurr = pPrev-next; i = 1; pPrev = pCurr; pCurr = pCurr-next; if (pPrev = pCurr) printf(t%d, pCurr-pos); free(pCurr

20、); break; i+; int main() int m = 0, n = 0; RingNodePtr pHead = NULL; printf(-Josephus Ring-n); printf(N(person count) = ); scanf(%d, &n); printf(M(out number) = ); scanf(%d, &m); if(n = 0 | m pos = 1; pHead-next = NULL; CreateRing(pHead, n); #ifdef _DEBUG PrintRing(pHead); #endif printf(nKick Order: ); KickFromRing(pHead, m); printf(t); system(pause); return 0; 5.上机体会 通过本次实验，使我掌握了使用Visual C+ 6.0上机调试的基本方法，以及用C语言实现线性表的顺序存储结构的定义和线性表的链式存储结构单链表的定义;熟悉了线性表在顺序存储结构即顺序表中的各种基本操作和线性表在链式存储结构单链表中的各种操作，还学会了约瑟夫环问题的算法。教师评价 优良 中及格不及格教师签名日期