数据结构（C语言版）
程序一/*尾插法建立一个单链表，并按顺序输出*/
#include<malloc.h>
#include<stdio.h>
#define NULL 0 /*宏定义*/
typedef struct node /*定义结点类型的数据结构*/
{
char c; /*数据域，类型为字符型*/
struct node *next; /*指针域，类型为本结构体类型*/
}*L; /*类型重定义，即Node和*L和struct node等价*/
main()
{
L l,p,q; /*用指针类型定义三个结点类型的指针*/
char ch;
l=(L)malloc(sizeof(L)); /*分配内存空间*/
l->c='\0'; /*为头结点的数据域赋值，值为空*/
l->next=NULL; /*指明下一个结点目前不存在*/
q=l; /*q为游动指针，链表结点的连结要用*/
printf("Input a character:\n");
scanf("%c",&ch);
getchar(); //此语句用来吸收键盘输入的回车符，没有其它含义
while(ch!='!') /*输入!表示输入结束*/
{
p=(L)malloc(sizeof(L)); /*为新输入的数据分配内存空间*/
p->c=ch;
p->next=NULL; /*新输入的结点在链表的最后，即它的后面没有其它元素*/
q->next=p; /*q用于将上一个元素链接至当前新元素*/
q=p; /*q自己移到当前最后一个元素，以备继续链接所用*/
scanf("%c",&ch);
getchar();
}
q=l; /*输入整个链表前，先将q移到链表头，l一般不动*/
while(q->next!=NULL) /*若q所指向的元素后面还有其它元素，则将该元素的数据输出*/
{
printf("%c-->",q->next->c); /*q->next->c表示q所指向的下一个元素的数据*/
q=q->next; /*完成该元素的输出后，q移至下一个元素重复输出操作*/
}
}
程序二
/*单链表的元素查找，按内容查找*/
#include<malloc.h>
#include<stdio.h>
#define NULL 0 /*宏定义*/
typedef struct node /*定义结点类型的数据结构*/
{
char c; /*数据域，类型为字符型*/
struct node *next; /*指针域，类型为本结构体类型*/
}*L; /*类型重定义，即Node和*L和struct node等价*/
main()
{
L l,p,q; /*用指针类型定义三个结点类型的指针*/
char ch;
int n;
l=(L)malloc(sizeof(L)); /*分配内存空间*/
l->c='\0'; /*为头结点的数据域赋值，值为空*/
l->next=NULL; /*指明下一个结点目前不存在*/
q=l; /*q为游动指针，链表结点的连结要用*/
printf("Input a character:\n");
scanf("%c",&ch);
getchar();
while(ch!='!') /*输入!表示输入结束*/
{
p=(L)malloc(sizeof(L)); /*为新输入的数据分配内存空间*/
p->c=ch;
p->next=NULL; /*新输入的结点在链表的最后，即它的后面没有其它元素*/
q->next=p; /*q用于将上一个元素链接至当前新元素*/
q=p; /*q自己移到当前最后一个元素，以备继续链接所用*/
scanf("%c",&ch);
getchar();
}
q=l; /*输入整个链表前，先将q移到链表头，l一般不动*/
while(q->next!=NULL) /*若q所指向的元素后面还有其它元素，则将该元素的数据输出*/
{
printf("%c-->",q->next->c); /*q->next->c表示q所指向的下一个元素的数据*/
q=q->next; /*完成该元素的输出后，q移至下一个元素重复输出操作*/
}
/*--------以上为建立一个单链表-------------*/
printf("\nInput a character you wanna find\n");
scanf("%c",&ch);
printf("\nthe character you wanna find is %c\n",ch);
q=l->next; /*q移至头结点的后一个元素，即实际第一个数据点*/
n=1; //位置计数器
while(q!=NULL) /*若q不为空，即该结点存在*/
{
if(q->c==ch) /*字符匹配*/
printf("character found in position %d\n",n);
q=q->next; /*移至下一个元素继续查找*/
n++;
}
}
程序三
/*元素插入操作*/
#include<malloc.h>
#include<stdio.h>
#define NULL 0 /*宏定义*/
typedef struct node /*定义结点类型的数据结构*/
{
char c; /*数据域，类型为字符型*/
struct node *next; /*指针域，类型为本结构体类型*/
}Node,*L; /*类型重定义，即Node和*L和struct node等价*/
main()
{
L l,p,q; /*用指针类型定义三个结点类型的指针*/
char ch;
int pos,n;
l=(L)malloc(sizeof(Node)); /*分配内存空间*/
l->c='\0'; /*为头结点的数据域赋值，值为空*/
l->next=NULL; /*指明下一个结点目前不存在*/
q=l; /*q为游动指针，链表结点的连结要用*/
printf("Input a character:\n");
scanf("%c",&ch);
getchar();
while(ch!='!') /*输入!表示输入结束*/
{
p=(L)malloc(sizeof(Node)); /*为新输入的数据分配内存空间*/
p->c=ch;
p->next=NULL; /*新输入的结点在链表的最后，即它的后面没有其它元素*/
q->next=p; /*q用于将上一个元素链接至当前新元素*/
q=p; /*q自己移到当前最后一个元素，以备继续链接所用*/
scanf("%c",&ch);
getchar();
}
q=l; /*输入整个链表前，先将q移到链表头，l一般不动*/
while(q->next!=NULL) /*若q所指向的元素后面还有其它元素，则将该元素的数据输出*/
{
printf("%c-->",q->next->c); /*q->next->c表示q所指向的下一个元素的数据*/
q=q->next; /*完成该元素的输出后，q移至下一个元素重复输出操作*/
}
/*以上为建立一个单链表*/
printf("Input the character and its position, such as s,3\n\n");
scanf("%c,%d",&ch,&pos);
q=l;
n=1;
while(n!=pos&&q->next!=NULL) /*未找到插入位置，且后面还有元素*/
{
q=q->next;
n++;
}
/*退出循环后，要么找到插入位置，要么表已到最后，输入的插入位置过大*/
if(n<pos) /*表已读完，仍未找到插入位置*/
printf("\n\nincorrect position, insert failed\n\n");
else /*找到插入位置*/
{
/*将进行插入操作*/
p=(L)malloc(sizeof(Node)); /*给新输入的数据分配内存空间*/
p->c=ch;
p->next=q->next;
q->next=p;
}
/*操作完成，然后输出新表*/
q=l; /*输入整个链表前，先将q移到链表头，l一般不动*/
while(q->next!=NULL) /*若q所指向的元素后面还有其它元素，则将该元素的数据输出*/
{
printf("%c-->",q->next->c); /*q->next->c表示q所指向的下一个元素的数据*/
q=q->next; /*完成该元素的输出后，q移至下一个元素重复输出操作*/
}
}
程序四
/*按内容元素删除操作*/
#include<malloc.h>
#include<stdio.h>
#define NULL 0 /*宏定义*/
typedef struct node /*定义结点类型的数据结构*/
{
char c; /*数据域，类型为字符型*/
struct node *next; /*指针域，类型为本结构体类型*/
}Node,*L; /*类型重定义，即Node和*L和struct node等价*/
main()
{
L l,p,q; /*用指针类型定义三个结点类型的指针*/
char ch;
int n;
l=(L)malloc(sizeof(Node)); /*分配内存空间*/
l->c='\0'; /*为头结点的数据域赋值，值为空*/
l->next=NULL; /*指明下一个结点目前不存在*/
q=l; /*q为游动指针，链表结点的连结要用*/
printf("Input a character:\n");
scanf("%c",&ch);
getchar();
while(ch!='!') /*输入!表示输入结束*/
{
p=(L)malloc(sizeof(Node)); /*为新输入的数据分配内存空间*/
p->c=ch;
p->next=NULL; /*新输入的结点在链表的最后，即它的后面没有其它元素*/
q->next=p; /*q用于将上一个元素链接至当前新元素*/
q=p; /*q自己移到当前最后一个元素，以备继续链接所用*/
scanf("%c",&ch);
getchar();
}
q=l; /*输入整个链表前，先将q移到链表头，l一般不动*/
while(q->next!=NULL) /*若q所指向的元素后面还有其它元素，则将该元素的数据输出*/
{
printf("%c-->",q->next->c); /*q->next->c表示q所指向的下一个元素的数据*/
q=q->next; /*完成该元素的输出后，q移至下一个元素重复输出操作*/
}
/*以上为建立单链表*/
printf("input the character you wanna delete\n\n");
scanf("%c",&ch);
printf("the element you wanna delete is %c\n\n",ch);
q=l->next;
p=l;
n=1;
while(q!=NULL&&q->c!=ch)
{
p=q;
q=q->next;
n++;
}
/*退出循环时可能找到指定元素，也可能表读完，需要进一步判断*/
if(q==NULL)
printf("element not found, delete failed\n\n");
else
p->next=q->next;
q=l->next; /*输入整个链表前，先将q移到链表头，l一般不动*/
while(q!=NULL) /*若q所指向的元素后面还有其它元素，则将该元素的数据输出*/
{
printf("%c-->",q->c); /*q->next->c表示q所指向的下一个元素的数据*/
q=q->next; /*完成该元素的输出后，q移至下一个元素重复输出操作*/
}
}
程序五
/*按位置删除元素*/
#include<malloc.h>
#include<stdio.h>
#define NULL 0 /*宏定义*/
typedef struct node /*定义结点类型的数据结构*/
{
char c; /*数据域，类型为字符型*/
struct node *next; /*指针域，类型为本结构体类型*/
}Node,*L; /*类型重定义，即Node和*L和struct node等价*/
main()
{
L l,p,q; /*用指针类型定义三个结点类型的指针*/
char ch;
int pos,n;
l=(L)malloc(sizeof(Node)); /*分配内存空间*/
l->c='\0'; /*为头结点的数据域赋值，值为空*/
l->next=NULL; /*指明下一个结点目前不存在*/
q=l; /*q为游动指针，链表结点的连结要用*/
printf("Input a character:\n");
scanf("%c",&ch);
getchar();
while(ch!='!') /*输入!表示输入结束*/
{
p=(L)malloc(sizeof(Node)); /*为新输入的数据分配内存空间*/
p->c=ch;
p->next=NULL; /*新输入的结点在链表的最后，即它的后面没有其它元素*/
q->next=p; /*q用于将上一个元素链接至当前新元素*/
q=p; /*q自己移到当前最后一个元素，以备继续链接所用*/
scanf("%c",&ch);
getchar();
}
q=l; /*输入整个链表前，先将q移到链表头，l一般不动*/
while(q->next!=NULL) /*若q所指向的元素后面还有其它元素，则将该元素的数据输出*/
{
printf("%c-->",q->next->c); /*q->next->c表示q所指向的下一个元素的数据*/
q=q->next; /*完成该元素的输出后，q移至下一个元素重复输出操作*/
}
/*以上为建立单链表*/
printf("Input the position\n");
scanf("%d",&pos);
p=l;
n=1;
while(p->next!=NULL&&n!=pos)
{
p=p->next;
n++;
}
/*退出循环后，可能找到删除的元素位置，可能表读完，需要进一步判断*/
if(n==pos) /*删除位置找到，删除该位置上的元素*/
{
p->next=p->next->next;
//free(p);
}
else
printf("incorrect position, delete failed\n");
q=l; /*输入整个链表前，先将q移到链表头，l一般不动*/
while(q->next!=NULL) /*若q所指向的元素后面还有其它元素，则将该元素的数据输出*/
{
printf("%c-->",q->next->c); /*q->next->c表示q所指向的下一个元素的数据*/
q=q->next; /*完成该元素的输出后，q移至下一个元素重复输出操作*/
}
}
程序六
//建立双向链表
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define NULL 0
typedef struct dlnode
{
char ch;
struct dlnode *pri,*next;
}dnode,*dl;
main()
{
dl l,p,q;
char c;
l=(dl)malloc(sizeof(dnode));
l->ch='\0';
l->next=NULL;
l->pri=NULL;
q=l;
printf("输入字符建立双向链表\n");
scanf("%c",&c);
getchar();
while(c!='!')
{
p=(dl)malloc(sizeof(dnode));
p->ch=c;
p->pri=q;
p->next=NULL;
q->next=p;
q=p;
scanf("%c",&c);
getchar();
}
q=l;
while(q->next!=NULL)
{
q=q->next;
printf("%c-->",q->ch);
}
printf("\n");
while(q->pri!=NULL)
{
printf("%c-->",q->ch);
q=q->pri;
}
printf("\n");
}
程序七
//单链表就地逆置
#include<stdio.h>
#include<malloc.h>
#define NULL 0 /*宏定义*/
typedef struct node /*定义结点类型的数据结构*/
{
char c; /*数据域，类型为字符型*/
struct node *next; /*指针域，类型为本结构体类型*/
}Node,*L; /*类型重定义，即Node和*L和struct node等价*/
main()
{
L l,p,q,r; /*用指针类型定义三个结点类型的指针*/
char ch;
l=(L)malloc(sizeof(Node)); /*分配内存空间*/
l->c='\0'; /*为头结点的数据域赋值，值为空*/
l->next=NULL; /*指明下一个结点目前不存在*/
q=l; /*q为游动指针，链表结点的连结要用*/
printf("Input a character:\n");
scanf("%c",&ch);
getchar();
while(ch!='!') /*输入!表示输入结束*/
{
p=(L)malloc(sizeof(Node)); /*为新输入的数据分配内存空间*/
p->c=ch;
p->next=NULL; /*新输入的结点在链表的最后，即它的后面没有其它元素*/
q->next=p; /*q用于将上一个元素链接至当前新元素*/
q=p; /*q自己移到当前最后一个元素，以备继续链接所用*/
scanf("%c",&ch);
getchar();
}
q=l; /*输入整个链表前，先将q移到链表头，l一般不动*/
while(q->next!=NULL) /*若q所指向的元素后面还有其它元素，则将该元素的数据输出*/
{
printf("%c-->",q->next->c); /*q->next->c表示q所指向的下一个元素的数据*/
q=q->next; /*完成该元素的输出后，q移至下一个元素重复输出操作*/
}
printf("\n");
//以上完成了单链表的创建
q=l->next;
p=q->next;
r=p->next;
q->next=NULL;
while(r!=NULL)
{
p->next=q;
q=p;
p=r;
if(r->next!=NULL) //r后面还有结点，则逆置继续
r=r->next;
else
break;
}
r->next=q;
l->next=r; //头结点指向最后一个结点
q=l; /*输入整个链表前，先将q移到链表头，l一般不动*/
while(q->next!=NULL) /*若q所指向的元素后面还有其它元素，则将该元素的数据输出*/
{
printf("%c-->",q->next->c); /*q->next->c表示q所指向的下一个元素的数据*/
q=q->next; /*完成该元素的输出后，q移至下一个元素重复输出操作*/
}
printf("\n");
}
程序八
//约瑟夫环问题
#include<stdio.h>
#include<malloc.h>
typedef struct lnode
{
int num;
struct lnode *next;
}node,*L;
main()
{
int amount,start,circle,n,c;
L p,l,q;
printf("一共有几个人围成一圈？\n");
scanf("%d",&amount);
getchar();
printf("从第几个开始计数？\n");
scanf("%d",&start);
getchar();
printf("每几人一次循环？\n");
scanf("%d",&circle);
getchar();
l=(L)malloc(sizeof(node)); //头结点
l->next=NULL;
l->num=0;
q=l;
n=0;
while(n++<amount)
{
p=(L)malloc(sizeof(node));
p->next=NULL;
p->num=n;
q->next=p;
q=p;
}
q->next=l->next; //形成循环链表
//以上完成了单向循环链表的建立
p=l->next;
q=l;
n=1;
while(n++<start)
{
p=p->next;
q=q->next;
}
//退出循环时p,q分别位于指定位置
//接下去进行周期性结点删除，直到链表只余一个结点为止
n=1; //n计算被删除的结点的数量，当n=amount-1时删除结束
while(n++<amount)
{
c=1; //c作为循环临时变量
while(c++<circle)
{
p=p->next;
q=q->next;
}
//删除当前p指向的结点
printf("删除结点%d\t",p->num);
q->next=p->next;
p=p->next;
}
printf("\n最后剩下%d\n",p->num);
}
不错！