数据结构—顺序表的实现

桃扇骨 2022-06-07 12:46 187阅读 0赞

#include<stdio.h>
    #include<stdlib.h>
    //顺序表的9种操作 
    /*
    bool InitList(SqList &L); 	  					//建立一个空的线性表 
    void CreateSqList(SqList &L,int m);          	//初始化线性表m个元素 
    int  SerachElem(SqList L, int e);				//查找与e相等的元素,返回e第一次出现的位序 
    void PrintList(SqList L);                  		//输出表中的元素
    bool UpdateList(SqList &L, int i, Elemtype x);  //将第i个元素更改为x 
    bool ListinSert(SqList &L, int i, Elemtype e);  //在第i个位置之前插入元素e  
    bool ListDelete1(SqList &L, int i,Elemtype &e); //删除第i个位置的元素并用e返回 
    int  ListLength(SqList L);						//返回线性表元素的个数
    void ClearList(SqList &L);						//将线性表L置为空表 
    */
    //当有一个指向结构的指针而不是结构体本身，且欲访问它的成员时，就要用->操作符而不是. 
    typedef int Elemtype;
    #define maxsize 10
    #define increase_size 100    //每次的增量 
    typedef struct{
    	Elemtype *data;          //存放数据的地方  
    	int length;             //表的当前长度 
    	int listsize;        	//表的储存容量 
    }SqList;
    bool InitList(SqList &L){
    	L.data = (Elemtype *)malloc(maxsize*sizeof(Elemtype));  //强制转换成Elemtype *的指针 
    	if(!L.data)           //空指针 
    		return false;
    	L.length = 0;
    	L.listsize = maxsize;
    	return true; 
    }
    void CreateSqList(SqList &L,int n){
    	//将n个元素依次加入线性表 
    	for(int i = 0; i < n; i++){
    		scanf("%d", &L.data[i]);
    		L.length++;
    		if(L.length >= L.listsize){    //增加表长 
    			Elemtype *newdata = (Elemtype *)realloc(L.data, (L.listsize + increase_size)*sizeof(Elemtype));
    			L.data = newdata;
    			L.listsize += increase_size;		
    		}			
    	}
    }
    bool ListinSert(SqList &L, int i, Elemtype e){
    	//在第i个元素之前插入元素e
    	//  1<=i<=L.length+1     i == 1时，其实就是插在data[0]的位置 
    	//                       i == L.length+1,就是在最后一个元素之后插入 
    	if(i < 1 || i > L.length + 1)
    		return false;
    	if(L.length >= L.listsize){   //增加表的长度 
    		Elemtype *newdata = (Elemtype *)realloc(L.data, (L.listsize + increase_size)*sizeof(Elemtype));
    		L.data = newdata;
    		L.listsize += increase_size; 
    	}
    	Elemtype *p, *q;
    	q = &(L.data[i-1]);   						  
    	for(p = &(L.data[L.length-1]); p >= q; p--)  //插入位置及之后的元素后移，注意数组下标是从零开始的 
    		*(p + 1) = *p;
    	*q = e;
    	L.length++;
    	return true; 
    } 
    bool ListDelete1(SqList &L, int i,Elemtype &e){  //不用指针的写法  
    	//删除表中第i个元素，并返回给e 
    	//  1 <= i <= L.length 
    	
    	if(i < i || i > L.length)
    		return false;
    	e = L.data[i-1];
    	int k;
    	for(k = i; k < L.length; k++)
    		L.data[k-1] = L.data[k];
    	L.length--;
    	return true;
    }
    bool ListDelete2(SqList &L, int i,Elemtype &e){  //用指针的写法   
    	if(i < i || i > L.length)
    		return false;
    	Elemtype *p, *q;
    	p = &L.data[i-1];
    	e = *p;
    	q = &L.data[L.length-1];                    //将表最后一个元素的地址给q 
    	for(++p; p <= q; p++)
    		*(p - 1) = *p;
    	L.length--;
    	return true;
    }
    int  ListLength(SqList L){    //返回线性表的长度 
    	return L.length;
    }
    int  SerachElem(SqList L, int e){
    	//查找与e相等的元素,返回e第一次出现的位序，没找到则返回0 
    	int result = 0;
    	for(int i = 0; i < L.length; i++){
    		if(L.data[i] == e){
    			result = i + 1;
    			break;
    		}
    	}
    	return result;
    } 
    void PrintList(SqList L){
    	for(int i = 0; i < L.length; i++)
    		printf("%d ", L.data[i]);
    	printf("\n");
    }
    void ClearList(SqList &L){
    	if(L.data != NULL){
    		free(L.data);
    		L.data = 0;
    		L.length = L.listsize  = 0;
    	}
    }
    bool UpdateList(SqList &L, int i, Elemtype e){
    	if(i < i || i > L.length)
    		return false;
    	L.data[i-1] = e;
    	return true; 
    }
    int main(){
    	SqList L; 
    	int n, i;
    	Elemtype e;
    	InitList(L);
    	printf("顺序表已经创建好啦，请输入你想添加的元素个数 n：\n");
    	scanf("%d", &n);
    	printf("请输入%d个元素：\n", n); 
    	CreateSqList(L, n);	
    	printf("顺序表的长度为：%d\n", ListLength(L));			
    	printf("请输入要插入的位置i和元素e：\n");
    	scanf("%d %d", &i, &e);
    	ListinSert(L, i, e);
    	printf("顺序表中的值有：\n");
    	PrintList(L);
    	printf("请输入你要删除的元素序号i :\n");
    	scanf("%d", &i);
    	ListDelete1(L, i, e);
    	printf("顺序表中的值有：\n");
    	PrintList(L);
    	printf("请输入你要查找的元素e :\n");
    	scanf("%d", &e);
    	if(SerachElem(L, e) == 0)
    		printf("Sorry，没找到这个元素\n");
    	else
    		printf("这个元素第一次出现的位置是：%d\n", SerachElem(L, e));			
    	printf("请输入要修改的位置i和元素e：\n");
    	scanf("%d %d", &i, &e);
    	UpdateList(L, i, e);
    	printf("顺序表中的值有：\n");
    	PrintList(L);
    	return 0;		
    }

![Image 1][]

[Image 1]: