数据结构总结（用于个人学习)

#数据结构总结（用于个人学习)| 来源: 网络整理| 查看: 265

此博客是用于本人学习，定义和代码来源于[数据结构(C语言版)].严蔚敏如果有错误，请指出（其实有阅读量就不错了...）

一.线性表

　　线性表是最常用且最简单的一种数据结构。简言之，一个线性表是n个数据元素的有序序列。至于数据元素的具体含义，在不同情况下各有不同，在后面你会看到元素都是以ElemType表示，因为这个元素在程序里面有可能是整形，浮点数，字符，更有可能是结构体，具体定义要看需求。

　　线性表有可能是(字符)（A,B,C,D....Z）,也有可能是(整形)（4,8,32,....100）,更有可能结构体，如下。

　　而在数据结构中，线性表的实现常见的有两种方式：顺序表示和链式表示。

　　1.顺序表示

　　线性表的顺序表示指的是一组地址连续的存储单元依次存存储线性表的数据元素。

　　在我的理解里面，其实线性表的顺序表示指的是是预先分配好一个相对比较大的空间，然后把数据元素一个个放进去，他们之间的位置是“物理相邻”的。

示意图

//---------线性表的动态分配顺序存储结构-------- #define LIST_INIT_SIZE 100 //线性表存储初始空间大小 #define LISTINCREMENT 10 //每次新增的空间大小 typedef struct { ElemType *elem; //存储空间基址,ElemType是基本的数据元素. //至于具体是什么就看你自己定义了，刚刚初学可以定义为int int length; //当前长度 int listsize; //分配的空间大小 }SqList;

　　这里只是总结一下线性表的核心操作：

　　1.初始化（Status InitList_Sq(SqList &List)）

　　2.线性表的第i个元素前插入e（Status ListInsert_Sq(SqList &L, int i, ElemType e)）

　　3.获取线性表的第i个数据（ElemType GetElem(SqList &L, int i) ）

　　4.删除线性表第i个元素（Status ListDelete_Sq(SqList &L,int i,ElemType e)）

　　下面逐个逐个介绍

　　1.线性表初始化

　　实现思路：在c语言里面，线性表的初始化是首先是先用malloc分配一个比较大的空间，然后用结构体的基地址elem指向该空间，初始化其他两个变量（分配空间，长度）

Status InitList_Sq(SqList &List){ List.elem = (ElemType*) malloc(LIST_INIT_SIZE * sizeof(ElemType)); if(!List.elem) exit(OVERFLOW); List.length=0; List.listsize = LIST_INIT_SIZE; return OK; }

　　2.数据插入

　　实现思路：首先是判断当前空间是否已经满了，如果已经满了，就增加分配空间。然后记录一下第i个元素的位置，也就是下标为i-1的元素的位置，把第i个元素的之后的元素（包含第i个元素）都向后移动一位，为新插入元素腾出位置，最后才把空出来的位置，即下标为i-1的位置存放元素。

插入示意图

Status ListInsert_Sq(SqList &L,int i, ElemType e){ ElemType *newbase,*q,*p; if(i-1>L.length || i= L.listsize){ newbase = (ElemType*)realloc(L.elem,LISTINCREMENT*sizeof(ElemType)); if(!newbase)exit(OVERFLOW); L.elem = newbase; L.listsize += LISTINCREMENT; } q = &L.elem[i-1]; for(p=&L.elem[L.length-1];p>=q;p--){ *(p+1)=*p; } *q = e; L.length++; return OK; }

　　3.获取线性表的第i个数据

　　这个其实是很简单的，在线性表里面，是直接根据首地址的之后的第i-1个位置的元素就可以了，

ElemType GetElem(SqList L, int i){ if(i>L.length || iL.length || idata; }

3.线性表的第i个元素前插入e

　　实现思路：初始化一个新的结点，找到该链表的第i个元素的前一个元素（要除去头结点），即第i结点的位置，然后把新结点的指针域指向第i结点的指针域所指的地址，第i结点的指针域指向新结点，这样就可以连起来了。观察下面示意图，假设p指向第i个元素，s指向新结点，第一步，先把p的指针域的位置赋给s的指针域，第二步，把p的指针域指向s，这两部不能交换，因为一旦交换，就会丢失原来p的后继结点。相当于把绳子砍断，然后两端的位置和新加入的绳子连接起来。

实现示意图

// 在L的第i个位置前插入e Status ListInsert_L(LinkList &L,int i,ElemType e){ LinkList q,p; if(idata = e; if(!q) exit(OVERFLOW); // 查找第i-1个元素 p = L; while(--i && p){ p=p->next; } if(!p) return ERROR; q->next = p->next; p->next = q; return OK; }

4.删除链表的第i个元素

　　实现原理:其实如果你理解上面两个操作，这个操作会很简单，首先查找第i-1个元素的位置，即第i个结点的位置，这里设为p，然后记录一下后继位置，设q，然后把p的后继位置指向q的后继位置，相当于把绳子砍掉一部分，然后再拼起来的感觉。

// 删除L的第i个位置的元素，并赋给e Status ListDelete_L(LinkList &L,int i,ElemType e){ LinkList q,p; if(inext; } // q为第i个位置 q = p->next; if(!q) return ERROR; p->next = q->next; free(q); return OK; }

最后附上代码下载地址。

顺序表下载地址

链表下载地址

如果有哪里写的不对或者问题的，请指出打脸~~万分感谢~~欢迎转载，但请在文章开头写原文链接，如果觉得对你有帮助的，请点击推介或者粉一个~~你的支持是我创造的动力

【本文地址】

数据结构总结（用于个人学习)

数据结构总结（用于个人学习)

今日新闻

推荐新闻