线性表的存储方式及其操作（C语言版） |
您所在的位置：网站首页 › 顺序表的线性存储结构数组c语言 › 线性表的存储方式及其操作（C语言版） |
线性表的存储方式及其操作（C语言版）
|
该篇也是复习数据结构总结的 ，虽然很简单 但方便以后使用。 线性表的顺序存储1.定义一个结构体，因为在高级语言中 数组具有随机存储的特性，所以通常用数组来表示顺序存储。 typedef struct LNode *List; struct LNode{ ElementType Data[maxsize]; int last; //线性表的长度为 last+1 }; struct LNode L; //定义了一个结构体 List PtrL; //定义了一个结构体指针 访问下标 i的元素为 L.Data[i] 或者为 Ptr-> Data[i]2.初始化操作 List MakeEmpty() { List PtrL; PtrL = (List)malloc(sizeof(struct LNode)); PtrL->last = -1; return PtrL; }3.查找操作 int Find(ElementType X,List PtrL) { int i = 0; while(ilast && PtrL ->Data[i] != X) i++; if(i>PtrL->last) return -1; else return i; }4.插入操作 时间复杂度为 O(N) void Insert(ElementType X,int i,List PtrL) { int j; if(PtrL->last == maxsize-1) { printf("表满"); return; } if(iPtrL->last+2) /*因为插入的是第 i个位置的元素 (1last;j>=i-1;j--) PtrL->Data[j+1]=PtrL->Data[j]; /* 将 ai ~an 倒序向后移动*/ PtrL->Data[i-1] = X; PtrL->last++; return; }5.删除操作 第i个元素 1Data[j-1] = PtrL->Data[j]; PtrL->last--; return; }
线性表的链式存储结构 1.结构体 typedef struct LNode *List; struct LNode{ ElementType Data; List Next; //线性表的长度为 last+1 }; struct LNode L; //定义了一个结构体 List PtrL; //定义了一个结构体指针 访问下标 i的元素为 L.Data[i] 或者为 Ptr-> Data[i]2.因为链表不像顺序表那样数组直接有表长，所以 我们加上一个求表长的操作。 int Length(List PtrL) { List p = PtrL; int j =0; while(p) /* p不为空*/ { p = p->Next; j++; } return j; }3.查找第K个元素 List FindKth(int K,List PtrL) { List p =PtrL; while(p!=NULL && iNext; i++; } if(i == K) return p; // 找到第K个返回指针 else return NULL; }3.2按值查找 List Find(ElementType X,List PtrL) { List p = PtrL; //临时变量设置为链表表头 while(P!=NULL && p->Data != X) p = p->Next; return p; }4.链表的插入， 这里一定要注意操作顺序
详细请看图示 List Insert(ElementType X,int i,List PtrL) { List p,s; if(i == 1) //新节点在表头 { s = (List)malloc(sizeof(struct LNode)); //申请、填装节点 s->Data = X; s->Next = PtrL; return s; //返回表头指针 } p = FindKth(i-1,PtrL); //查找第 i-1个节点 if(p == NULL) //第 i-1 个节点不存在，不能插入 { printf("参数i错"); return NULL; } else { s = (List)malloc(sizeof(struct LNode)); //申请填装节点 s->Data = X; s->Next = p->Next; //新节点插入在第 i - 1个节点的后面 p->Next = s; // 注意里 两句的顺序不能改变 ！！！ return PtrL; // 返回新的链表的头指针 } }5.删除操作 List Delete(int i,List PtrL) //删除第i个节点 { List p,s; if(i == 1) // 如果删除的是表的第一个节点 { s = PtrL; // s指向第一个节点 if(PtrL != NULL) PtrL = PtrL->Next; //从链表中删除 else return NULL; free(s); return PtrL; } p = FindKth(i-1,PtrL); if(p == NULL) { printf("第%d个节点不存在",i-1);return NULL; } else if(p->Next == NULL) { printf("第%d个节点不存在",i); return NULL; } else { s = p->Next; // s指向第i个节点 p->Next = s->Next; //从链表中删除 free(s); // 释放被删除节点 return PtrL; } }
由于刚开始学的时候书上的是C++版本，搞了半天才搞懂，而且网上查的都觉得不对劲，自己从新写了一遍提供大家和我自己参考。后续更新更多关于数据结构的内容。谢谢大家啊 |
【本文地址】
今日新闻 |
推荐新闻 |