[数据结构与算法]数据结构—线性表

线性表的操作

（一）单链表的操作

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

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

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

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

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

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

//链式存储的线性表
/*
李子木
*/

#include<stdio.h>
#include<malloc.h>
#include<time.h>
#include<stdlib.h>
#include<math.h>
typedef 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 && i<K){
		p = p->Next;
		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<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#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->Last

List 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;j<L->Last;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;
}