线性表的实现

系统管理员 2021-09-12 02:48 456阅读 0赞

线性表的定义，初始化，插入和删除及打印输出

#include <stdio.h>
    #include<malloc.h>
    #include<stdlib.h>
    
    //线性表存储空间的初始分配量
    #define List_Init_Size 100
    //线性表的存储空间的分配增量
    #define List_Increment 10
    
    typedef struct{
    	int *elem;
    	int length;
    	int listsize;
    }SqList;
    
    //对于线性表进行初始化
    void InitList_Sq(SqList &L){
    	//构造一个空的线性表
    	L.elem = (int *)malloc((List_Init_Size)* (sizeof(int)));
    	if (!L.elem)exit(1);
    	L.length = 0;
    	L.listsize = List_Init_Size;
    }
    
    //向线性表的第i个位置插入数据
    bool List_Insert_Sq(SqList &L, int i, int num){
    	//检查i的合法性
    	if (i < 1 || i > L.length + 1){
    		return false;
    	}
    	//如果当前存储空间已满，则再分配空间给该线性表
    	if (L.length >= L.listsize){
    		int * newbase = (int *)realloc(L.elem, (L.listsize + List_Increment)* sizeof(int));
    		if (!newbase)return false;
    		//赋值新地址
    		L.elem = newbase;
    		//增加存储空间
    		L.listsize += List_Increment;
    	}
    	//自第i个元素依次先后移动一个
    	for (int j = L.length - 1; j >= i; j--){
    		L.elem[j + 1] = L.elem[j];
    	}
    	L.elem[i - 1] = num;
    	L.length++;
    	return true;
    }
    
    //删除线性表中的第i个元素,并返回
    bool ListDelete_Sq(SqList &L, int i,int &num){
    	//检查i的合法性
    	if (i < 1 || i > L.length)return false;
    	//将被删除的元素赋值给num
    	num = L.elem[i - 1];
    	//元素依次前移
    	for (int j = i - 1; j < L.length-1; j++){
    		L.elem[j] = L.elem[j + 1];
    	}
    	L.length--;
    	return true;
    }
    
    //输出线性表
    void Print(SqList &L){
    	for (int i = 0,index = 1; i < L.length; i++){
    		if(index < 10){
                printf("%5d ", L.elem[i]);
                index++;
    		}else{
                printf("%d\n", L.elem[i]);
                index = 1;
    		}
    	}
    }
    
    int main()
    {
    	SqList list;
    	InitList_Sq(list);
    	for(int i = 1;i < 108;i++){
            List_Insert_Sq(list,i,i);
    	}
    	Print(list);
    	int temp = 0;
    	ListDelete_Sq(list,2,temp);
    	printf("\n删除的元素：%d\n",temp);
    	printf("删除后的线性表：\n");
    	Print(list);
    	return 0;
    }

![Center][]

[Center]: /images/20210911/e626e1d936c84264a71dde2b1c18ec7d.png