前言
本菜鸟笔者打算入门一下数据结构，在学习过程中通过自己简单话术总结相关基础知识要点，希望能帮助同样在入门的小伙伴们快速了解相关基础知识的轮廓，然后根据知识点再进一步的学习和理解。整个系列采用c语言来实现，代码会提供注释，方便理解实现思路。
逻辑结构
线性表是0个或多个的有穷序列，(k_0) 是(k_1)的前驱，(k_1)是(k_0)的后继，除了首尾结点以外每个结点元素都有且只有一个前驱和一个后继（类似于现实生活中排队）。
物理存储结构
一、顺序表
- 概念：采用一组相邻且连续的存储空间存储元素。即：存储一个元素需要2个单位地址空间，从1号开始存储，则第二个元素存储首地址为3号，以此类推。代码实现中常用 数组作为顺序表元素的存储。
- 优缺点
- 优点：方便查找，确定首地址就可以查找任意下标的元素。由此可以随机存取。
- 缺点：不易于插入删除，由于顺序表中元素地址是相邻的，当插入或者删除一个元素后，修改位置之后的所有元素都需要移动，空间开销大（类比排队中一个人出或者插入到队伍中，后面的所有人都需要向前或向后移动）
- 代码实现（初始化增删改查）
#include
#include
#define MAXMIUM 100 //定义数组容量最大值
/*结构体*/
typedef struct SeqList
{
int element[MAXMIUM];//存放整型数据的数组
int n;//数组元素个数
}SeqList;
/*初始化，创建一个顺序表*/
SeqList *createNullSeq()
{
SeqList *list = (SeqList *)malloc(sizeof(SeqList));
if (list == NULL)
{
printf("wrong");
}
else
{
list->n = 0;//初始化的数组内没有元素，所以n=0
}
return list;
}
/*在指定下标位置插入元素*/
int insert(SeqList* list , int data,int index){
if(list->n < MAXMIUM && indexn){//插入前数组个数不能达到上限，下标需要在有效范围内
int i;
for(i=list->n-1;i>=index;i--){//当前插入元素的位置和位置后的元素都需要往后移动一位
list->element[i+1] = list->element[i];
}
i++;
list->element[i] = data;
list->n++;
return 1;
}
return 0;
}
/*删除指定位置的元素*/
int delete(SeqList* list,int index){
if(indexn-1&&index>=0){//跟插入类似，判断有效条件
for(int i=index;in-1;i++){//删除的位置以及后面的元素都需要往前移动一格
list->element[i] = list->element[i+1];
}
list->n--;
return 1;
}
return 0;
}
/*简单线性表判空*/
int isNull(SeqList* list){
return list->n==0?1:0;
}
/*查找元素*/
int locate_seq(SeqList* list,int data){
if(list->n==0){
return -1;
}
for(int i=0;in;i++){
if(list->element[i]==data){
return i;
}
}
return -1;
}
/*获得指定下标的元素*/
int find(SeqList* list,int x){
if(x>=0||xn){
return list->element[x];
}
return -1;
}
二、链表
- 原理 顺序表插入删除需要大量空间损耗（因为需要移动），所以可以采用链表的方式减少损耗。每个结点元素在存储元素信息时（数据域），还需要额外存储一个指针域，用于存储指向下一个结点的地址。这样相邻结点之间的地址无需相邻。插入删除时只需要修改相关指针域即可。
- 优缺点
- 优点：插入删除空间代价小，只需要直接修改指针域。
- 缺点：查找麻烦，每次查找都需要从头结点遍历。
- 代码实现（初始化增删改查）
#include <stdio.h>
#include <stdlib.h>
typedef struct PNode
{
struct PNode *next;
int data;
} PNode;
PNode *createNullNode()
{
PNode *node = (PNode *)malloc(sizeof(PNode));
if (node == NULL)
{
printf("wrong");
return NULL;
}
node->next = NULL;
node->data = 0;
return node;
}
/*带头结点插入*/
int insertNode(PNode *list, int i, int data)
{
if (list == NULL)
{
printf("null");
return 0;
}
int p = 0;
while (list->next != NULL)
{
if (p != i)
{
list = list->next;
p++;
}else{
break;
}
}
if (p == i)
{
PNode *temp = list->next;
PNode *node = createNullNode();
node->next = temp;
node->data = data;
list->next = node;
return 1;
}
printf("out of range");
return 0;
}
/*带头结点删除第一个值为x的结点*/
int delete(PNode *list,int x){
if(list==NULL){
printf("list is null");
return 0;
}
while(list->next!=NULL&&list->next->data!=x){
list = list->next;
}
if(list->next!=NULL&&list->next->data==x){
PNode* temp = list->next;
list->next = temp->next;
temp->next = NULL;
free(temp);
return 1;
}
printf("no found %d",x);
return 0;
}
/*通过下标查找元素，带头结点*/
PNode *find(PNode* list,int i){
if(list==NULL){
printf("null list ");
return NULL;
}
int cursor = 0;
while(list->next!=NULL&&cursor!=i){
list = list->next;
cursor++;
}
if(cursor==i){
printf("find %d",list->next->data);
return list->next;
}
printf("out of range");
return NULL;
}
/*判空*/
int isNull(PNode* list){
return list==NULL?1:list->next==NULL?1:0;
}
int main()
{
PNode *head = createNullNode();
int flag = isNull(head);
printf("%d\n",isNull(head));
insertNode(head,0,1);
insertNode(head,1,2);
insertNode(head,2,3);
insertNode(head,3,4);
insertNode(head,2,77);
// find(head,2);
printf("%d",isNull(head));
}
</stdlib.h></stdio.h>
总结
- 链表方便增删，顺序表方便查找
- 链表的增删主要通过修改指针，顺序表增删主要通过移动元素。
Original: https://www.cnblogs.com/allworldg/p/15339910.html
Author: allworldg
Title: 数据结构简单话（一）线性表
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/583402/
转载文章受原作者版权保护。转载请注明原作者出处！