数据结构—线性表

线性表的操作

（一）单链表的操作

（1）用随机函数生成8个3位整数（100~999），把这些整数存于单链表中；

（2）输出单链表的内容；

（3）读入一个整数，查看该整数是否在表中，若在，输出其位置（首位置为1）；

（4）读入一个整数，以及要插入的位置，把该整数插入到单链表中，输出单链表的内容（要求判断输入的位置是否合理）；

（5）读入一个整数，若该整数在单链表里，删除该整数，输出单链表的内容；

（6）把链单表的内容翻转，输出单链表的内容。

//链式存储的线性表/*李子木*/#include#include#include#include#includetypedef int ElementType; // ElementType 可定义为任意类型typedef struct LNode *List;struct LNode{	ElementType Data;   //数据域 	List Next;   // 下一个链表的地址 }; List L;List MakeEmpty(); //初始化链表 int Length(List L);  // 以遍历链表的方法求链表长度 List FindKth(int K,List L);  // 按序号查找 int Find(ElementType X,List L);  // 按值查找 List Insert(ElementType X,int i,List L);  //将 X 插入到第 i-1(i>0) 个结点之后 List Delete(ElementType X,List L); // 删除第 i(i>0) 个结点 void Print(List L); // 输出链表元素 List biu1(List L);	//内容反转（迭代）List biu2(List L);	//内容反转（递归）// 初始化链表 List MakeEmpty(){	List L = (List)malloc(sizeof(struct LNode));	List p = (List)malloc(sizeof(struct LNode));	L = p;	srand((unsigned)time(NULL));	for(int i = 0;i < 8;i++){		p->Data=rand()%900+100;		if(i<7){			p->Next=(List)malloc(sizeof(struct LNode));			p=p->Next;		}	}	p->Next=NULL;	return L;}//求表长 int Length(List L){	List p = L;	int len=0;	while(p){  // 当 p 不为空 		p = p->Next;		len++;	}	return len;} // 按序查找 List FindKth(int K,List L){	List p = L;	int i = 1;  //从 1 开始 	while(p && iNext;		i++;	}	if(i == K)    // 找到了 		return p;	else    // 未找到 		return NULL;} // 按值查找  int Find(ElementType X,List L){	List p = L;	int len=1;	while(p && p->Data!=X){		p=p->Next;		len++;	}	if(p==NULL)	return -1;	return len;   } /* 插入1. 用 s 指向一个新的结点2. 用 p 指向链表的第 i-1 个结点 3. s->Next = p->Next，将 s 的下一个结点指向 p 的下一个结点 4. p->Next = s，将 p 的下一结点改为 s   */List Insert(ElementType X,int i,List L){	List p,s;	if(i == 1){     // 新结点插入在表头 		s = (List)malloc(sizeof(struct LNode));		if(s==NULL){			printf("分配内存错误！");			return L;		}		s->Data = X;		s->Next = L;		return s;     //插入的结点为头结点 	}	p = FindKth(i-1,L);   // 找到第 i-1 个结点	if(!p){   // 第 i-1 个结点不存在 		printf("结点错误");		return NULL;	}else{		s = (List)malloc(sizeof(struct LNode));		if(s==NULL){			printf("分配内存错误！");			return L;		}		s->Data = X;		s->Next = p->Next;   //将 s 的下一个结点指向 p 的下一个结点 		p->Next = s;   // 将 p 的下一结点改为 s		return L;	}}/* 删除1. 用 p 指向链表的第 i-1 个结点 2. 用 s 指向要被删除的的第 i 个结点3. p->Next = s->Next，p 指针指向 s 后面4. free(s)，释放空间 */List Delete(ElementType X,List L){	List p,s;	int k;	k=Find(X,L);	if(k==1){   //如果要删除头结点 		s = L;		if(L)   // 如果不为空 			L = L->Next;		else			return NULL;		free(s);   // 释放被删除结点 		return L; 	}	p = FindKth(k-1,L);    // 查找第 i-1 个结点	if(!p || !(p->Next)){     // 第 i-1 个或第 i 个结点不存在 		printf("结点错误");		return NULL;	}else{		s = p->Next;    // s 指向第 i 个结点 		p->Next = s->Next;  //从链表删除 		free(s);  // 释放被删除结点 		return L;	}}// 输出链表元素 void Print(List L){	List t;	int flag = 1;	printf("当前链表为：");	for(t = L;t;t =t->Next){		printf("%d  ",t->Data);		flag = 0;	}	if(flag)		printf("NULL");	printf("/n"); }//内容反转（迭代）List biu1(List L) {	List p,s;	p = (List)malloc(sizeof(struct LNode));	p = L;	if (L == NULL || L->Next == NULL) {		return L;	}	s = NULL;	while (p != NULL) {		List tmp = p->Next;   //暂存p后面一个元素		p->Next = s;    		s = p;			//p->Next指向前一个元素		p = tmp;   //p指向原始链表的下一个元素	}	return s;}//内容反转（递归）List biu2(List L) {	if (L == NULL || L->Next == NULL) {		return L;	}	List s = biu2(L->Next);	L->Next->Next = L;	L->Next = NULL;	return s;}int main() {	List L;	L = MakeEmpty();	int x, k;	Print(L);	printf("请输入一个整数：");	scanf("%d", &x);	if (Find(x, L) == -1) {		printf("查无此值！/n");	}	else {		printf("该值所在位置为：%d/n", Find(x, L));	}	printf("请输入需要插入的元素值以及插入位置：");	scanf("%d%d", &x, &k);	L = Insert(x, k, L);	Print(L);	printf("请输入需要删除的元素：");	scanf("%d", &x);	L = Delete(x, L);	Print(L);	system("pause");   //等待用户按任意键，然后返回, 等同于getchar()	L = biu1(L);	printf("执行链表反转.../n");	system("pause");	Print(L);	L = biu2(L);	printf("执行链表反转.../n");	system("pause");	Print(L); 	return 0;}

（二）顺序表的操作

（1）用随机函数生成8个3位整数（100~999），把这些整数存于顺序表中；

（2）输出顺序表的内容；

（3）读入一个整数，查看该整数是否在顺序表中，若在，输出其位置（首位置为1）；

（4）读入一个整数，以及要插入的位置，把该整数插入到顺序表中，输出顺序表的内容（要求判断输入的位置是否合理）；

（5）读入一个整数，若该整数在顺序表里，删除该整数，输出顺序表的内容；

（6）把顺序表的内容翻转，输出顺序表的内容。

//顺序存储的线性表/*李子木*/#include#include#include#include#include#define MAXSIZE 100  // MAXSIZE 定义为 Data 数组的大小typedef int ElementType;  // ElementType 可定义为任意类型typedef struct LNode *List; struct LNode{   ElementType Data[MAXSIZE];    int Last;  // Last 定义线性表的最后一个元素};List L;//访问下标为 i 的元素：L->Data[i]//线性表的长度：L->LastList MakeEmpty(); //初始化顺序表 int Find(ElementType X,List L); //查找 X 第一次出现的下标 void Insert(ElementType X,int i,List L); //在下标为 i 的地方插入 X void Delete(int i,List L);   //删除下标为 i 的当前值 ElementType FindS(int i,List L);  //返回下标为 i 的当前值int Length(List L);  //返回顺序表的长度     可以不用，但不能不会 void biu(List L);  //使线性表内内容反转   //初始化 List MakeEmpty(){    List L;    L = (List)malloc(sizeof(struct LNode));    L->Last = 0;    return L;}// 按值查找 int Find(ElementType X,List L){    int i=1;    while(i <= L->Last && L->Data[i] != X)          i++;    if(L->Last < i)  //如果没找到，返回 -1        return -1;     else    // 找到后返回下标         return i;}// 插入void Insert(ElementType X,int i,List L){    int j;    if(L->Last == MAXSIZE-1){  //位置已满         printf("表满");        return;    }    if(i < 0 || L->Last + 1 < i){  //位置越界        printf("位置不合法");        return;    }    for(j=L->Last;j>=i;j--)   // 从后往前依次向后挪一个          L->Data[j+1] = L->Data[j];       L->Data[i] = X;    //新元素插入    L->Last++;    // Last仍然指向最后元素    return;} //删除void Delete(ElementType x,List L){	if(L->Last==0){		printf("空表");		return;	}	int i,j;	for(i=1;i<=L->Last;i++){		if(L->Data[i]==x){			for(j=i;jLast;j++)  //被删除的元素后面的元素前移 			L->Data[j]=L->Data[j+1];  			L->Last--;  //Last指向最后元素 			return;		}	}	printf("未找到该值");}//按下标查找 ElementType FindS(int i,List L){	if(i < 0 || L->Last < i)  return;	return L->Data[i];}//表长 int Length(List L){	return L->Last; }//内容反转void biu(List L){	int i,t;	for(i=1;i<=((L->Last+1)/2);i++){		t=L->Data[i];		L->Data[i]=L->Data[L->Last-i+1];		L->Data[L->Last-i+1]=t;	}}int main(){	List L;	L=MakeEmpty();	int i,x;	srand((unsigned)time(NULL));   //设置种子，使得产生的随机数是可变化的 	for(i=1;i<=8;i++){  //插入三个随机100-999之间的整数		Insert(rand()%900+100,i,L);  	}  	printf("单链表中的内容为：");	for(i=1;i<=8;i++)  //输出链表中的的内容 	printf("%d ",L->Data[i]);	printf("/n");	printf("请输入一个整数：");	scanf("%d",&x);	if(Find(x,L)!=-1) 	printf("查找值为%d的下标为：%d/n",x,Find(x,L));	if(Find(x,L)==-1)	printf("未找到该值/n");	printf("请输入需要插入的整数：");	scanf("%d",&x);	Insert(x,L->Last+1,L);	printf("此时单链表中的内容为：");	for(i=1;i<=9;i++)	printf("%d ",L->Data[i]);	printf("/n");	printf("请输入需要删除的整数：");	scanf("%d",&x);	Delete(x,L);	printf("删除元素后单链表中的内容为："); 	for(i=1;i<=L->Last;i++)	printf("%d ",L->Data[i]);	printf("/n");	biu(L);	printf("内容反转后链表中内容为：");	for(i=1;i<=L->Last;i++)	printf("%d ",L->Data[i]); 	return 0;}