《实验一 线性表及其应用-----顺序表.docx》由会员分享，可在线阅读，更多相关《实验一 线性表及其应用-----顺序表.docx（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、实验一线性表及其应用顺序表ttinclude ttinclude ftdefine MAXSIZE 100 typedef int ElemType; typedef struct list (ElemType* elem;指针定义数组 int listsize;int length;Sqlist;void initlist_sq(Sqlist* L) L-elem =(ElemType*)malloc(MAXSIZE * sizeof (ElemType);if (!L-elem) exit (0);L-length = 0;I-listsize = MAXSIZE;)在线性表L的第n个元素
2、之前插入元素xvoid insert_sq(Sqlist* L, int n, ElemType x) ( int i;if (n L-length + 1) 检查插入位置n的合法性 (printf (插入的位置n非法！ n)； return;)if (L-length = L-listsize) 检查线性表是否为满 printf (线性表满了！ n)； return;for (i = L-length; i = n; i-)L-elemi=L-elemi - 1;插入点之后的元素循环后移一个位置 L-elemn - 1=x; 将代插入的元素存入到下标为nT的位置L-length+; 修改线性
3、表的长度 )利用插入方法实现创立指定长度的线性表Lvoid creat_sq(Sqlist* L) (int tablen, i = 1;ElemType temp;printf (请输入顺序表的长度n);scanf (z，%d，z, fetablen);char *base;char *top;int stacksize;sqstack;=二=4戈s的初始化，此时栈s非空，其内初始时有一个元素行= void initstack(sqstack *s)(s-base=(char *)malloc(100*sizeof(char);if(!s-base) exit (0);*(s-base)二#
4、;s-top=s-base+l;s-stacksize=100;)=获取栈s的栈顶元素=char gettop(sqstack *s)判定栈是否为空，假设为空，请请输出提示信息“栈空”并返回kif ( s-base 二二 s-top)(printf (栈空! n);return 0;if (s-top=s-base) exit (0);return *(s-top-l);)=在栈中插入一个新的元素e=void push(sqstack *s, char *e)(检查栈是否为满，假设为满，请输出提示信息“栈满”，并退出程序if ( s-base = s-top)printf (栈空！ n);re
5、turn;*(s-top+)=*e;)=出栈操作=void pop(sqstack *s)判定栈是否为空，假设为空，请输出提示信息“栈空”，并退出程序if( s-base + s-stacksize = s-top) (printf (栈空! n);return;s-top一;)void main()(char a30, *c;int flag = 0;int choice = 1;sqstack sq;while (choice)flag = 0;initstack (&sq);printf Cshu ru biao da shi:n)； scanf(%s, a);c=a;while(*c!
6、=0)(if(*c= ( | |*c= ，I *c=，) push(&sq,c);if (*c=)if (gettop(&sq)=，()pop(&sq);else(printf(non);flag = 1;break;if(*c=)if (gettop (&sq)=)pop(&sq);else(printf (non);flag = 1;break;if (*c=)if (gettop(&sq)=，)pop (&sq);else(printf (non);flag = 1;break;) c+;if(!flag)if(gettop(&sq)= #) printf (yesn);elseprin
7、tf(non);printf(请输入你的选择：1继续,0退出n);scanf(%d, &choice);)实验四队列及其应用 ftincludestdio.h #includestdlib.h #define ElemType int typedef struct qnode定义记录类型int data;节点数据域为datastruct qnode *next; QNode;typedef structQNode *front, *rear;QuType;在队列qu中查找一个节点，其数据域的值为Num,找到返回1,否那么返回-1 int QuSearch (QuType *qu, int Nu
8、m) QNode *p=qu-front;循环查找节点P，P的数据域的值为Numwhile( p & p-data != Num ) p=p-next;找到数据域值为Num的节点，返回1if( p )/ if(p-data=no) ? ?return 1;elsereturn -1;/打印队列中所有的元素 void QuDisplay(QuType *qu) (QNode *p=qu-front;int i=l;if (p=NULL) printf (*没有排队者*n);while(p != NULL) printf (第%(1个排队者为:%5dn，i+, p-data); p=p-next;
9、)入队操作，在队列qu中插入节点，该节点的数据域的值为Numint EnQueue (QuType *qu, int Num) QNode *q=(QNode *)malloc(sizeof(QNode);if (q=NULL)return -1;节点q为即将插入的新节点，为其数据域赋值为Num,指针域赋值为NULL q-data = Num;q-next = NULL;if ( qu-rear=二NULL ) /插入前队列中没有节点，如何插入新节点 (qu-front = q;qu-rear = q;else /插入前队列中有假设干节点，如何插入新节点 (qu-rear-next = q;q
10、u-rear = q;)return 1;/出队操作，删除队列中的队头节点，并用Num保存删除节点的数据 int OutQueue (QuType *qu, int *Num)QNode *p=qu-front;判断队列是否为空，假设队列为空，那么返回-1if( p = NULL )return -1;else 假设队列非空，那么删除队头节点使用Num获取队头节点数据域的值*Num = p-data;队列中只有一个节点P，删除方法？if ( p = qu-rear )qu-front = qu-rear = NULL;队列中有多于1个节点的时候，删除队头节点P的方法？ elsequ-front
11、 = p-next;free (p);return 1;)判空队列，假设为空返回1,否那么返回-1int QueueEmp(QuType *qu)(队列为空的条件？if( qu-front = NULL )return 1;elsereturn -1;)void main(void)(int sei,no,temp, flag=l;QuType *qu;qu=(QuType *)malloc(sizeof(QuType);qu-front=qu-rear=NULL;while(1二二flag)(printf(nl:排队2：就诊3：查看队列4：不再排队，余下就诊5：下班 n请选择);scanf(
12、%d, &sel);switch (sei)(case 1: printf(输入病历号：)；scanf(%d, &no);while(l=QuSearch(qu, no)输入后需要判断是否重复 (printf (输入病历号重复，请重新输入)； scanf(d, &no);EnQueue (qu,no)：break;if( OutQueue(qu, &temp)二二-1 )printf (*没有排队的病人*n); elseprintf (病历号为(的请就诊n，temp);break;QuDisplay (qu);break;if(QueueEmp(qu)=1)printf (*没有排队的病人*n
13、); else(printf (病人按如下顺序就诊n);QuDisplay(qu);flag=O;break;printf(已下班，请排队的病人明天就医！ n);flag=0;break;default:break;)getchar ();)实验五二叉树及其应用#include#include/二叉树的二叉链表存储表示typedef struct bitnode(char data;struct bitnode *lchild,*rchild;bitnode,*bitree;/=先序遍历 构造二叉树t =bitree createbitree()char c;bitree t;printf (
14、please input a word: nz，);getchar ();c=getchar ();if(c=t=NULL;else/为树中节点t分配存储空间t = (bitree)malloc(sizeof(bitnode);为节点t数据域赋值为获取的字符c t-data = c;/为节点t左子树赋值 t-lchild = createbitree();为节点t右子树赋值 t-rchild = createbitree ();return t;)=中序遍历二叉树void inordertraverse (bitree t)(if (t)(/中序遍历t的左子树 inordertraverse(
15、t-lchild);访问(打印)t的数据域 printf (，z%c t，t-data);中序遍历t的右子树 inordertraverse(t-rchiId);)=前序遍历=void pretraverse(bitree t)(if (t)(/访问(打印)t的数据域printf (z，%c t，t-data);先序遍历t的左子树pretraverse(t-lchild);先序遍历t的右子树pretraverse(t-rchild);=后序遍历=void backtraverse (bitree t)(if (t)(后序遍历t的左子树 backtraverse(t-lchild);后序遍历t的
16、右子树 backtraverse(t-rchiId);访问(打印)t的数据域 printf (c t，t-data);)void delete all (bitree t)(if (t)(删除t的左子树delete all(t-lchild);删除t的右子树delete_all(t-rchild);访问(打印)t的数据域，并删除节点t printf (c t，t-data);free (t);)void main()bitree T;char cmd;printf (Z，C: CreateTree I: Inorder P: PreOrder B: backOrdern)；while (1)
17、(cmd= getchar (); switch(cmd) (case C:case c :T=createbitree();printf (The Tree was Created !n)； break;case r :case i :inordertraverse(T); printf(n); break;case P，: case p:pretraverse(T); printf(n); break;case B:case b:backtraverse(T); printf(n); break;case X:case x:delete_all(T); printf(n); exit (0
18、);default:break;)printf (Z，C: CreateTreeI: Inorder P: PreOrder B: backOrder n)；getchar ();)getchar ();)实验六图的邻接矩阵和邻接表存储 ttinclude #include#define MAX_VERTEX_NUM 20最大顶点数typedef int AdjMatrix MAX_VERTEX_NUM MAX_VERTEX_NUM ; /邻接矩阵类型 typedef int VertexType;邻接矩阵定义 typedef struct (VertexType vexs MAX_VERTE
19、X_NUM;顶点表AdjMatrix arcs;邻接矩阵int vexnum, arcnum;图的顶点数和弧数 MGraph; 用邻接矩阵表示的图的类型MGraph/邻接表定义边结点类型定义(链表中的节点类型定义) typedef struct ArcNodeint adjvex;struct ArcNode *nextarc; int info;ArcNode;邻接表定义(表中头节点类型定义)typedef struct VNodeVertexType data;ArcNode *firstarc;VNode, AdjListMAX_VERTEX_NUM;/用邻接表表示的图的类型ALGrap
20、h的定义typedef structAdjList vertices; 邻接表 int vexnum, arcnum;ALGraph;ttdefine INF 32767打印图g的邻接矩阵 void DispMat(MGraph *g) (int i, j;for (i=0; ivexnum; i+)建立邻接矩阵 (for(j=0;jvexnum ;j+) if (g-arcs i j=INF)printf (%3s, );else printf(%3d, g-arcsi j); printf (n);/图用邻接矩阵表示为g,用邻接表表示为G,将g转换成Gvoid MatToList(MGra
21、ph *g, ALGraph *G) int i, j, n=g-vexnum;ArcNode *p;/G=(ALGraph *)malloc(sizeof(ALGraph);生成邻接表，即n条带头结点的空的单链表 for(i=0;iverticesi. firstarc=NULL;二重循环扫描邻接矩阵外重循环控制扫描邻接矩阵的第i行for(i=0;in;i+)内重循环控制扫描邻接矩阵的第j歹U;扫描至右向左进行printf (请输入 %d 个数据n，tablen); do(scanf (z/%dz，, &temp); 输入待插入的元素 tempinsert_sq(L, i, temp); 将
22、元素temp插入到线性表L的第i个位置 i+；修改i的值，以便下一次进行插入 while (i = tablen) & (i listsize); )打印线性表中的所有元素 void display_sq(Sqlist* L) |int i;i = 0; do (打印线性表L中下标为i的元素 printfL-elemi); while (+i length);printf (ri*顺序表打印完毕*nn);)在线性表L中查找元素x,假设存在范围其位置；假设不存在返回0 int Search sq(Sqlist* L, ElemType x) (int i;i = 0; do比拟线性表中下标为i的
23、元素与指定值x是否相等，假设相等，返回其位置i+1if (L-elemi二二 x)return i + 1; while (+i length); return 0;)查找线性表L中的第n个元素，返回其值ElemType Search_sq_byV(Sqlist* L, int n)/检查n的取值是否合法，假设非法返回0if (n L-length) return 0;return L-elemn - 1; 假设n取值合法，返回线性表L中下标为nT的元素)删除线性表L中的第n个元素 void delete sq(Sqlist* L, int n) | int i;if (n L-length)
24、 检查删除的位置n的合法性for ( j = n-1 ; j = 0 ; j)(if( g-arcsij != 0 ) 假设邻接矩阵的第i行第j列元素非零 (为边节点P分配存储空间p = (ArcNode *)malloc(sizeof(ArcNode);为节点P的数据域info赋值为非零元素的值p-info = g-arcsij;为节点P的数据域adjvex赋值为非零元素的列标jp-adjvex = j;为边节点P的指针域赋值为第i条单链表的头结点的指针域p-nextarc = G-verticesi. firstarc;将边节点p连接在第i条单链表的头结点之后 G-verticesi. f
25、irstarc = p;)循环结束时，完成了图G的邻接表的生成为图G的属性vexnuni赋值G-vexnum = g-vexnum ;为图G的属性arcnum赋值G-arcnum = g-arcnum;)打印图g的邻接表void DispAdj(ALGraph *G)(int i;ArcNode *p;for (i=0; ivexnum; i+)建立邻接矩阵p=G-verticesi. firstarc;if (p!=NULL)printf (z，%3d：z，, i);while(p!=NULL)(printf(%3d, p-adjvex);p=p-nextarc;)printf (n);)图
26、用邻接矩阵表示为g,用邻接表表示为G,将G转换成gvoid ListToMat (ALGraph *G, MGraph *g)int i, i, n=G-vexnum; Z XX z，ArcNode *p;生成图g的邻接矩阵，初始化为n行n列的全0矩阵for(i=0;in;i+)for(j=0;jarcsij=0;循环访问图G的邻接表，即访问n条单链表 for(i = 0 ; i verticesi. firstarc;/ P非空时，循环访问链表中的节点while( p ) (/获取节点P的数据域adjvex,并将其赋值给列标j； j = p-adjvex ;修改图g的邻接矩阵的第i行第j列的
27、元素的值，将其改为节点P的数据域 info的值g-arcsij = p-info;修改节点P，让其指向其后继 p = p-nextarc; 内重循环完成对邻接矩阵的第i行的修改 外重循环结束时，图g的邻接矩阵生成完毕为图g的属性vexnum赋值g-vexnum = G-vexnum;为图g的属性arcnum赋值 g-arcnum = G-arcnum;)void main (void)MGraph g,gl;ALGraph *G;int i, j;int A 6 =(0,5,0, 7, 0, 0),0, 0, 4, 0, 0, 0,8, 0, 0, 0, 0,9),o, 0, 5, 0, 0,
28、 6),0, 0,0, 5, 0, 0, 3, 0,0,0, 1,0)； 邻接矩阵内容g. vexnum=6;g. arcnum= 10;for (i=0; ig. vexnum; i+)建立邻接矩阵for(j=0;jg. vexnum ;j+) g. arcsi j=Ai j;)printf (n);printf(有向图G的邻接矩阵为：n)；DispMat(&g);G= (ALGraph *)malloc(sizeof(ALGraph);printf(图G的邻接矩阵转成邻接表：n)；MatToList(&g, G);DispAdj (G);printf(图G的邻接表转成邻接矩阵：n)；Lis
29、tToMat(G, &gl);DispMat(&gl);getchar ();)实验七排序#include ttinclude ttinclude ttdefine MENU printfCl:直接插入排序(按学号)2：简单项选择择排序(按姓名) 3：简单项选择择排序(按学号)4：冒泡排序 0：退出n)ttdefine MAXSIZE 100 typedef struct stulong stuNo;char stuName10; ElemType;typedef struct listElemType *elem; int listsize; int length;Sqlist;ElemTy
30、pe Stu10ElemType Stu10ElemType Stu10101,张三，口08,李四, 102,王五, 109,孙进, 104,赵六, 103,孙俪, 106,陈妍, 105,李静, 110,周平, 107,郑涛;/* 初始化顺序表 */void initlist_sq(Sqlist *L) /初始化顺序表L-elem=(ElemType *)malloc(MAXSIZE*sizeof(ElemType); if(!L-elem) exit(0);L-length=0;L-listsize=MAXSIZE;void creat_sq(Sqlist *L)int tablen, i
31、=0;printf (请输入要创立的线性表的长度(小于10): );scanf(%d, fetablen);do(L-elemi = Stui;i+；L-length+;while(ielem+i)-stuNo, (L-elem+i)-stuName ) )while(+ilength);printf(nn);)void fz(Sqlist &L1, Sqlist L)int n = L.length;for(int i = 0; i length ;for(i = 1 ; i elemi. stuName , L-elemil. stuName ) elemi;j 二 i-1；doL-ele
32、mj+1 = L-elemj;while(strcmp(temp. stuName , L-elemj. stuName)elemj+1 = temp ;)void sort insert ByNo(Sqlist L) / 按学号直接插入排序ElemType temp;int i, j, t=0;int n = L.length ;for(i = 1 ; i n ; i+)if( L. elemi. stuNo L. elemi-l. stuNo ) temp = L. elemi;j = i-1；doL. elemj+1= L. elemj;J；while( temp. stuNo leng
33、th ;for (i = 0 ; i n-l ; i+)k = i;for( j = i + 1; j elemj. stuNo elemk. stuNo ) k = j；if ( k != i )temp = L-elemi;L-elemi = L-elemk;L-elemk = temp ;)void sort_select_ByName(Sqlist *L)/ 按姓名排序ElemType temp;int i, j, k;int n = L-length ;for (i = 0 ; i n-l ; i+)k 二 i;for( j = i + 1; j elemj. stuName , L
34、-elemk. stuName)elemi;L-elemi = L-elemk;L-elemk= temp ;)/* 冒 泡排序 */void sort_bubble_ByNo(Sqlist *L)/ 按学号排序(ElemType temp;int i, j, flag;int n = L-length ;for(i = 0; i n - 1; i+)flag = 0;for(j = i; j elemj+l. stuNo elemj. stuNo) (temp = L-elemj;L-elemj = L-elemj+1;L-elemj+1 = temp ;flag = 1;if( flag
35、!= 1) break;void main()(Sqlist L, LI;int ch;initlist_sq(&L);initlist_sq(&L1);creat_sq(&L);fz(Ll,L);displaysq (&L1);MENU ;while (1)(printf (请输入你的选择：);scanf&ch);switch (ch) (case 0:exit (0);break;case 1:fz(Ll,L);printf(排序前的数据为：n);display_sq(&L1);sort insert ByNo (LI); printf(排序后的数据为：n); display_sq(&L1
36、);MENU ; break; case 2: fz(Ll,L); printf(排序前的数据为:n); display_sq(&Ll);sort_select_ByName(&L1); printf(排序后的数据为：n); display_sq (&L1);MENU ; break;case 3:fz (L1,L);printf(排序前的数据为:n)； display_sq(&Ll);sort_select_ByNo(&L1);printf(排序后的数据为:n)； displaysq(&L1);MENU ; break; case 4: fz (L1,L); printf(排序前的数据为:n
37、); display_sq(&L1);sort_bubble_ByNo(&L1);printf (排序后的数据为:n)； displaysq(&L1);MENU ; break; ) )实验八查找 ttinclude #include ttinclude #define MENU printfCl:创立表2:顺序查找3:折半查找4:打印表 0：退出 n)ttdefine MAXSIZE 100 typedef struct stu (long stuNo;char stuName10; ElemType; typedef struct list (ElemType *elem; int lis
38、tsize; int length;Sqlist;ElemType Stu10 = 101, 张三，口08, 李四, 102, 王五，口09, 孙进，口04, 赵六, 103,孙俪, 106,陈妍, 105,李静，”10,周平, 107,郑涛;/* 初始化顺序表 */void initlist_sq(Sqlist *L) 初始化顺序表L-elem= (ElemType *)malloc(MAXSIZE*sizeof(ElemType); if(!L-elem) exit(0);L-length=0;L-listsize=MAXSIZE;/ * 仓 ij 建顺序表 */ void creat_s
39、q(Sqlist *L)int tablen, i=0;printf (请输入要创立的线性表的长度(小于10): );scanf(%d，&tablen);doL-elemi = Stui;i+；L-length+; while(ielem+i)-stuNo, (L-elem+i)-stuName )while(+ilength); printf(nn);/* 直接插入排序 */void sort_insert (Sqlist *L)/按学号直接插入排序ElemType temp;int i, j, t=0;int n = L-length ;for(i = 1 ; i elemi. stuNo elemi-l. stuNo )j = i-1；doL-elemj+l= L-elemj;J；while(temp. stuNo elemj. stuNo & j = 0); L-elemj+1 = temp ;)/* 立接插入排序 */void sort_insert_byName(Sqlist *L)/ 按姓名直接插入排序ElemType temp;int i, j, t=0;int n = L-length ;for (i = 1 ; i elemi. stuName , L-elemi-l. stuName ) elemi;j = i-1； do