数据结构

2024-07-17 20:38| 来源: 网络整理| 查看: 265

线性结构顺序表和链表的实现及各种操作合集线性表顺序储存的实现结构体的定义顺序表的初始化插入操作删除操作按值查找应用举例删除自第i个元素开始的k个元素链表的实现不含头结点的链表的实现结构体定义线性表的创建线性表的长度计算按序号查找按值查找插入操作删除操作应用举例俩有序链表的合并

线性表顺序储存的实现结构体的定义 const int MAX_SIZE=10; struct Seplist{ int data[MAX_SIZE]; int last;//表长last+1,表空时last=-1 }; 顺序表的初始化 //顺序表初始化 Seplist *init_Seplist() { Seplist *L; L = (Seplist*)malloc(sizeof(Seplist)); L->last = -1; return L; } 插入操作

算法思路：

第一步——检查判断线性表的存储空间是否已满，若已满，则进行“溢出”处理检查i值是否超出允许的范围(1≤i≤len+1)，若超出，则进行“超出”处理第二步——进行操作如果上述条件都允许,则将最后一个元素到第i个元素依次向后移动一个位置将新的数据元素写到第i个位置上第三步——收尾线性表的长度增加1,插入成功 void insert_Seplist(Seplist *L,int i,int x)//在L的第i个位置插入x { //第一步，检查正确性 if(iL->last+2)//首先判断输入是否准确 { printf("i有错"); return; } if(L->last == MAX_SIZE - 1) { printf("空间已满"); return ; } //第二步，做相关处理 for(int j=L->last+1;j>i;j--) L->data[j] = L->data[j-1]; //收尾处理 L->data[i-1] = x ; L->last++; return ; } 删除操作

在这里插入图片描述

void delete_Seplist(Seplist *L,int i)//删除L表中的i号元素 { if(i L->last+1) { printf("i有错\n"); return ; } for(int j=i-1;jlast;j++) { L->data[j] = L->data[j+1]; } L->last--; return ; } 按值查找 int Location(Seplist *L,int x)//按值查找 { int i=0; for(int i=0;ilast+1;i++) { if(L->data[i] == x) return i; } return -1; } 应用举例删除自第i个元素开始的k个元素

算法分析：

（1）分析数据的正确性

（2）将第i+k元素后的元素向前移动K位

（3）将表长减k

void del_Seplist(Seplist *L,int i,int k) { if(ilast) { cout data[i+k-1]; i++; t--; } L->last-=k;*/ int t=k; while(t >0) { delete_Seplist(L,i); //i++; t--; } }

代码中给出了两种方法（注释中有一种）

链表的实现不含头结点的链表的实现结构体定义 struct Linklist{ int data; Linklist *next; }; 线性表的创建 //在尾部插入，建立线性表的链式储存 Linklist *creat_Linklist() { Linklist *L=NULL; Linklist *s,*r=NULL; int x; cin >> x ; for(;x!=flag;) { s = new Linklist; s->data = x; if(L == NULL) L=s; else r->next = s ; r=s; cin >> x; } if(r) r->next = NULL; return L; } 线性表的长度计算

在这里插入图片描述

int length(Linklist *L)//L是不带头节点的单链表 { Linklist *p = L; int len = 0; while(p) { len++; p = p->next; } return len; } 按序号查找

在这里插入图片描述

//在线性表中按序号查找 Linklist *Get_Linklist(Linklist *L,int i) { Linklist *p = L; int j=1; for(;j Linklist *p = L; while(p && p->data != data ) { p = p ->next; } return p; } 插入操作

在这里插入图片描述

//在线性表中第i个位置插入元素data bool ins_Linklist(Linklist *L,int i,int data) { Linklist *p ; Linklist *s; p = Get_Linklist(L,i-1); if(p == NULL) {cout Linklist *p,*s; p = Get_Linklist(L,i-1); if(p == NULL) { cout s = p->next; p->next =s->next; delete s; return 1; } } 应用举例俩有序链表的合并

算法分析：

主要思想：

两指针平行移动，一次扫描完成

算法分析：

1)在两条链的开始处设置2个临时指针;

2)如果2个指针中有一个为空，则转到步骤7;

3)将当前2个节点与其数据进行比较;

4)如果这2个节点可以添加，就添加这2个节点;

5)否则将数据域较小的节点链接到到结果链（c链表）;

6)继续搜索下一个节点转到步骤2;

7)将左节点复制到结果链;

8)返回结果链;

//将按值有序递增的链表la、lb归并为同样递增的lc， Linklist *link_Linklist(Linklist *la,Linklist *lb) { Linklist *lc,*p; int flag=0; while(la != NULL && lb != NULL) { if(la->data > lb->data) { if(flag==0) { lc=lb; p=lc; flag++; } else { lc->next=lb; lc=lc->next; } lb=lb->next; } else { if(flag==0) { lc=la;flag++; p=lc; } else { lc->next=la; lc=lc->next; } la=la->next; } } if(la != NULL) lc->next=la; else lc->next=lb; return p; }

【本文地址】

公司简介

联系我们

今日新闻

推荐新闻

专题文章