数据结构之顺序表(C++和C语言)

太过爱你忘了你带给我的痛 2023-02-11 03:25 12阅读 0赞

参考资料：《数据结构与算法（第四版）》机械工业出版社  
**顺序存储**指在内存中用地址连续的一块存储空间顺序存放线性表的各元素。（一片连续的存储空间）

### 文章目录 ###

*   *   *  顺序表的初始化，插入，删除，查找，显示
         *  顺序表合并

### 顺序表的初始化，插入，删除，查找，显示 ###

C语言代码：[顺序表 C语言版][C]  
C++代码：

#include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #define N 100010 
    using namespace std;
    
    //定义顺序表类型 
    typedef struct{ 
    	int data[N];  //定义元素为int类型
    	int last;  //起指针作用，指向最后一个元素的位置
    }SeqList;
    
    //顺序表初始化 
    SeqList *init_SeqList(){ 
    	SeqList *L;
    	L=(SeqList *)malloc(sizeof(SeqList));  //开辟一个新空间
    	L->last=-1;   //表长为 last+1
    	return L;
    }
    
    //顺序表的插入
    int Insert_SeqList(SeqList *L,int i,int x){ 
    	int j;
    	if(L->last==N-1){    //表长为 last+1, 表的最大长度为 N
    		cout<<"顺序表已满"<<endl; 
    		return -1;
    	}
    	if(i<1||i>L->last+2){    //可插入的范围 1 ~ last+1+1
    		cout<<"位置错误"<<endl;
    		return 0; 
    	}
    	for(j=L->last;j>=i-1;j--)   //将 i位置后的所有元素向后移动一个位置，直至空出插入的那个位置
    		L->data[j+1]=L->data[j];
    	L->data[i-1]=x;
    	L->last++;
    	return 1;
    } 
    
    //顺序表的删除
    int Delect_SeqList(SeqList *L,int i){ 
    	int j;
    	if(i<1||i>L->last+1){    //可删除的范围 1 ~ last+1
    		cout<<"不存在"<<endl;
    		return 0; 
    	}
    	for(j=i;j<=L->last;j++)    //将 i位置后的所有元素向前移动一个位置，直至覆盖需要删除的那个元素
    		L->data[j-1]=L->data[j];
    	L->last--;     //表长-1
    	cout<<"删除成功"<<endl;
    	return 1;
    } 
    
    //顺序表查找
    int Location_SeqList(SeqList *L,int x){ 
    	int i=0;
    	while(i<=L->last&&L->data[i]!=x)   //查询的位置不超过表长，当查询到元素时，结束循环
    		i++;
    	if(i>L->last) return -1;
    	else return i;
    }
    
    //顺序表的显示
    void show(SeqList *L) { 
    	printf("顺序表所有元素："); 
    	for(int i=0;i<=L->last;i++)
    		cout<<L->data[i]<<" ";
    	cout<<endl;
    }
    
    //主函数
    int main()
    { 
    	
    	int n;    //n为操作步骤次数
    	SeqList *L;    //定义一个链表
        L=init_SeqList();   //调用函数初始化顺序表
        printf("插入操作：I字母 位置 元素 | 删除操作：D字母 位置 | 查找操作：C字母 元素 | 显示操作：S字母\n 请输入操作次数：");
        scanf("%d",&n);
        getchar();
        while(n--) 
        { 
            char c;
            scanf("%c",&c);
            getchar();
            if(c=='C')    //查找元素所在位置
            { 
                int b;
                scanf("%d",&b);
                getchar();
                cout <<"该元素处于第"<< Location_SeqList(L,b) +1 <<"个位置"<< endl;
    
            }
            else if(c=='I')    //在 a位置插入元素 b
            {  
                int a,b;
                scanf("%d%d",&a,&b);
                getchar();
                Insert_SeqList(L,a,b);
            }
            else if(c=='D')     //删除 a位置的元素
            { 
                int a;
                scanf("%d",&a);
                getchar();
                Delect_SeqList(L,a);
            }
            else if(c=='S'){    //显示链表中所有元素
            	show(L);
    		}
        }
    	return 0;
    }

![顺序表代码实现][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70]

### 顺序表合并 ###

void merge(SeqList *A,SeqList *B,SeqList *C){ 
    	int i=0,j=0,k=0;
    	while(i<=A->last&&j<=B->last)
    		if(A->data[i]<=j<=B->data[j])
    			C->data[k++]=A->data[i++];
    		else
    			C->data[k++]=B->data[j++];
    	while(i<=A->last) 
    		C->data[k++]=A->data[i++];
    	while(j<=B->last) 
    		C->data[k++]=B->data[j++];
    	C->last=k-1;
    }

[C]: https://paste.ubuntu.com/p/2cDBGrn6xY/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200521165004968.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw==,size_16,color_FFFFFF,t_70