数据结构-线性表.doc

线性表 1：队列的基本操作 #include stdio.h#define MAXN 26char qMAXN;int head = -1, tail = -1;int en_queue(x)char x;if (tail = MAXN-1)return(1);q+tail = x;return(0);int de_queue(p_y)char *p_y;if (head = tail)return(1);*p_y = q+head;return(0);main() int i;char ch_x,ch_y;printf(input the char you want to enqueuen);scanf(%c,&ch_x);while(ch_x!=0)if (en_queue(ch_x)=1) printf(failure!n);elseprintf(success!n);printf(input a char for ch_x to enqueuench_x=);getchar();scanf(%c,&ch_x);i=1;while(qi!=0)printf(%c , qi);i+;if (de_queue(&ch_y)=1) printf(failure!n);elseprintf(success!n);printf(The dequeue char is %cn,ch_y);for (i=head+1; i=tail; i+)printf(%c , qi);2：链表和循序表的操作单链表基本操作的实现问题描述要在带头结点的单链表h中第i个数据元素之前插入一个数据元素x ，首先需要在单链表中寻找到第i-1个结点并用指针p指示，然后申请一个由指针s 指示的结点空间，并置x为其数据域值，最后修改第i-1个结点，并使x结点的指针指向第i个结点，要在带头结点的单链表h中删除第i个结点，首先要计数寻找到第i个结点并使指针p指向其前驱第i-1个结点，然后删除第i个结点并释放被删除结点空间。基本要求用链式存储结构实现存储实现提示链式存储结构不是随机存储结构，即不能直接取到单链表中某个结点，而要从单链表的头结点开始一个一个地计数寻找。程序实现# include # include typedef char DataType ;typedef struct node DataType data; /*结点的数据域*/ struct node *next; /*结点的指针域*/ListNode;void Init_List(ListNode *L)(*L)=(ListNode *)malloc(sizeof(ListNode);/*产生头结点*/(*L)-next=NULL;int List_Length(ListNode *L )int n=0;ListNode *p=L-next;while(p!=NULL)n+;p=p-next;return n;ListNode* GetNode(ListNode *L,int i) int j; ListNode *p; p=L;j=0; /*从头结点开始扫描*/ while(p-next&j!=i) /*顺指针向后扫描,直到p-next为NULL或i=j为止*/ p=p-next; j+; if(i=j) return p; /*找到了第i个结点*/ else return NULL; /*当i0时,找不到第i个结点*/ void InsertList(ListNode *L,DataType x,int i) ListNode *p,*s; p=GetNode(L,i-1); /*寻找第i-1个结点*/ if (p=NULL) /*in+1时插入位置i有错*/ printf(position error); return ; s=(ListNode *)malloc(sizeof(ListNode); s-data=x;s-next=p-next;p-next=s; void DeleteList(ListNode *L ,int i)ListNode *p,*r;p=GetNode(L,i-1); /*找到第i-1个结点*/if (p=NULL|p-next=NULL) /*in时,删除位置错*/ printf(position error); return ; r=p-next; /*使r指向被删除的结点a*/p-next=r-next; /*将ai从链上删除*/free(r); /*使用头插法建立带头结点链表算法*/ListNode * CreatListF(void)char ch;ListNode *head=(ListNode *)malloc(sizeof(ListNode); /*生成头结点*/ListNode *s; /*工作指针*/head-next=NULL; ch=getchar(); /*读入第1个字符*/while(ch!=n) s=(ListNode *)malloc(sizeof(ListNode); /*生成新结点*/ s-data=ch; /*将读入的数据放入新结点的数据域中*/ s-next=head-next; head-next=s; ch=getchar(); /*读入下一字符*/return head; /*使用尾插法建立带头结点链表算法*/ListNode * CreatListR1(void) char ch; ListNode *head=(ListNode *)malloc(sizeof(ListNode); /*生成头结点*/ ListNode *s,*r; /*工作指针*/ r=head; /*尾指针初值也指向头结点*/ while(ch=getchar()!=n) s=(ListNode *)malloc(sizeof(ListNode); s-data=ch; r-next=s; r=s; r-next=NULL; /*终端结点的指针域置空,或空表的头结点指针域置空*/ return head; /*复制链表A中的内容到表B中*/ void copy(ListNode *a, ListNode *b) ListNode *pa=a-next; ListNode *u; ListNode *rb=b; while(pa!=NULL) u=( ListNode *)malloc(sizeof(ListNode); u-data=pa-data; rb-next=u; rb=u; pa=pa-next; rb-next=NULL;/*输出带头结点的单链表*/void DisplaySL(ListNode *la, char *comment) ListNode *p ; p=la-next ; if(p) printf(n%sn , comment) ; while(p) printf(%4c,p-data); p=p-next; printf(n) ;/*主函数*/main( ) ListNode *la ,*lb,*lc, *p ;int n,x,i;printf(nyong tou cha fa jian li lian biao la，qing shu ru jie dian neirong:);la=CreatListF();DisplaySL(la,xin shengcheng de jiedian neirong:);printf(nlianbiao de changdu %2d,List_Length(la);printf(nqing shuru yao charu de yuansu:);scanf(%c,&x) ;printf(nqing shuru yao charu de weizhi:);scanf(%d,&i) ;InsertList(la,x,i);DisplaySL(la,charu hou jiedian de neirong:);printf(nqing shuru yao shanchu jiedian de weizhi:);scanf(%d,&i);DeleteList(la,i);DisplaySL(la, shanchuhou jiedian de neirong:);printf(nyong weichafa jianli lianbiao ,qing shuru lianbiaobeirong:);fflush(stdin);lb=CreatListR1();DisplaySL(lb,xinshengchengjiedian de neirong:);Init_List(&lc);copy(la,lc);DisplaySL(lc,fuzhi shengcheng de lcjiedianeirong:);getch();顺序表的插入删除 #define MAXSIZE 100int listMAXSIZE;int n;/*insert in a seq list*/int sq_insert(list, p_n, i, x)int list , x;int *p_n, i;int j;if (i*p_n) return(1);if (*p_n=MAXSIZE) return(2);for (j=*p_n+1; ji; j-)listj=listj-1;listi=x;(*p_n)+;return(0);/*delete in a seq list*/int sq_delete(list, p_n, i)int list ;int *p_n, i;int j;if (i=*p_n) return(1);for (j = i+1; j=*p_n; j+)listj-1 = listj;(*p_n)-;return(0);main()int i,x,temp;printf(please input the number for nn);printf(n=);scanf(%d,&n);for (i=0; i=n; i+)printf(list%d=,i);scanf(%d,&listi);printf(The list before insertion isn);for (i=0; i=n; i+) printf(%d ,listi);printf(n);printf(please input the position where you want to insert a valuenposition=);scanf(%d,&i);printf(please input the value you want to insert.nx=);scanf(%d,&x);temp=sq_insert(list,&n,i,x);switch(temp)case 0:printf(The insertion is successful!n);printf(The list is after insertion isn);for(i=0; i=n; i+) printf(%d ,listi);printf(n);printf(%dn,n);break;case 1:case 2:printf(The insertion is not successful!n);break;/*deleting*/printf(The list before deleting isn);for (i=0; i=n; i+) printf(%d ,listi);printf(n);printf(please input the position where you want to delete a valuenposition=);scanf(%d,&i);temp=sq_delete(list,&n,i);switch(temp)case 0:printf(The deleting is successful!n);printf(The list is after deleting isn);for(i=0; i=n; i+) printf(%d ,listi);printf(n);printf(%d,n);break;case 1:printf(The deleting is not successful!);break;循环链表循环链表实验约瑟夫环问题问题描述设有N个人围坐一圈，现从某个人开始报数，数到M的人出列，接着从出列的下一个人开始重新报数，数到M的人以出列，如此下去，直到所有人都出列为此。试设计确定他们的出列次序序列的程序。基本要求 选择单向循环链表作为存储结构模拟整个过程，并依次输出列的各人的编号。实现提示 程序运行之后，首先要求用户指定初始报数的下限值，可以n=30,此题循环链表可不设头节点，而且必须注意空表和非空表的界限。如 n=8, m=4 时，若从第一个人， 设每个人的编号依次为 1，2，3，开始报数，则得到的出列次序为4，8，5，2，1，3，7，6，如下图所示，内层数字表示人的编号 ，每个编号外层的数字代表人出列的序号。程序实现#include #include typedef struct node int num; struct node *next; linklist;linklist *creat(head,n) /*使n个人围成一圈，并给每个人标识号数*/ linklist *head; int n ; linklist *s,*p; int i; s=(linklist * )malloc(sizeof(linklist); head=s; s-num=1; p=s; for(i=2;inum=i; p-next=s; p=s; p-next=head; return(head); /* creat */linklist * select(linklist *head, int m) linklist *p, *q; int i, t; p=head; t=1; q=p; /* q为p的前趋指针*/ p=p-next; do t=t+1 ; /*报一次数*/ if(t%m=0) printf(%4d, p-num); q-next=p-next; free(p); p=q-next; else q=p; p=p-next; while(q!=p); head=p; printf(%4d,p-num); return (head); /* select */main( ) int n,m; linklist *head; printf(ninput the total number:n=); scanf(%d, &n); printf(ninput the number to call:m=); scanf(%d, &m); head=creat(head,n); head=select(head,m); printf(nthe last one is :%d, head-num); /* main */3：栈的操作 链式栈 #include stdio.h#include alloc.hstruct nodechar data; struct node *link;typedef struct node NODE;NODE * top = NULL;void push_l(x)char x;NODE *p; p = (NODE * )malloc(sizeof(NODE); p-data = x; p-link = top; top = p;int pop_l(p_y)char *p_y;NODE *p; if (top = NULL)return(1); * p_y = top-data; p = top; top = top-link; free(p); return(0);main()NODE *p;char ch_x,ch_y;printf(input the char you want to pushn);scanf(%c,&ch_x);while(ch_x!=0)push_l(ch_x);getchar();scanf(%c,&ch_x);p=(NODE*)malloc(sizeof(NODE);p=top;while(p!=NULL)printf(%c ,p-data);p=p-link;printf(n);if (pop_l(&ch_y)=1)