下载文档原格式
数据结构-线性结构线性表线性表是最简单最常见的数据结构,属于逻辑结构;线性表有两种实现⽅式(存储⽅式),分别是顺序实现和链接实现;定义:线性表是由n(>=0)个数据元素组成的有限序列,数据元素的个数n定义为表的长度;术语:前驱, 后继, 直接前驱, 直接后继, 长度, 空表案例:线性表⽤L表⽰,⼀个⾮空线性表可记为L = (a1,a2,..an);a1后⾯的称为a1的后继an前⾯的称为an的前驱a1为起始节点,an为终端节点,任意相邻的两个元素,如a1和a2,a1是a2的直接前驱,a2是a1的直接后继;线性表中元素个数即表的长度,此处为n;表中没有任何元素时,称为空表除了⾸节点和尾节点之外,每个节点都有且只有⼀个直接前驱和直接后继,⾸节点没有前驱,尾节点没有后继;节点之间的关系属于⼀对⼀;线性表的基本运算初始化Initiate(L) 建⽴⼀个空表L(),L不包含数据元素求表长度Length(L) 返回线性表的长度取表元素Get(L,i) 返回线性表的第i个元素,i不满⾜1<=i<=Length(L)时,返回特殊值;定位Locate(L,x)查找x在L中的节点序号,若有多个匹配的返回第⼀个,若没有匹配的返回0;插⼊Insert(L,x,i)将x插⼊到L的第i个元素的前⾯(其他元素往后挪),参数i取值范围为1<=i<=Length(L)+1;运算结束后表长度+1;删除Delete(L,i)删除表L中的第i个元素,i有效范围1<=i<=Length(L);操作结束后表长度-1强调:上述的第i个指的是元素的序号从1开始,⽽不是下标从0开始;另外:插⼊操作要保证操作后数据还是⼀个接着⼀个的不能出现空缺;线性表的顺序存储实现线性表是⼀种逻辑结构,可以通过顺序存储结构来实现,即:将表中的节点⼀次存放在计算机内存中⼀组连续的存储单元中,数据元素在线性表中的邻接关系决定了它们在存储空间中的存储位置;换句话说逻辑结构中相邻的两个节点的实际存储位置也相邻;⽤顺序存储结构实现的线性表也称之为为顺序表,⼀般采⽤数组来实现;图⽰:⼤⼩与长度:线性表的⼤⼩:指的是最⼤能存储的元素个数线性表的长度:指的是当前已存储的个数⽰例:c语⾔实现:#include <stdio.h>//初始化操作:const MAX_SIZE = 5;//最⼤长度typedef struct list {int data[MAX_SIZE];//数组int length;//当前数据长度};//获取targert在表中的位置int locate(struct list *l,int target){for (int i = 0;i < l->length;i++){if (target == l->data[i]){return i + 1;}}return 0;}//获取第loc个元素int get(struct list *l,int loc){if (loc < 1 || loc > l->length){printf("error:位置超出范围\n");return -1;}else{return l->data[loc-1];}}//插⼊⼀个元素到第loc个位置上void insert(struct list *l,int data,int location){if (l->length == MAX_SIZE){printf("errolr:表容量已满\n");return;}if (location < 1 || location > l->length+1){printf("error:位置超出范围\n");return;}//⽬标位置后⾯的内容以此往后挪for (int i = l->length; i >= location; i--) {l->data[i] = l->data[i-1];}//在⽬标位置放⼊新的数据l->data[location-1] = data;l->length+=1;//长度加1}//删除第loc个元素,从⽬标位置往后的元素⼀次向前移动void delete(struct list *l,int loc){if (loc < 1|| loc > l->length){printf("error:位置超出范围\n");return;}//⽬标位置及后⾯的所有元素全部向后移动for (;loc < l->length; ++loc) {l->data[loc-1] = l->data[loc];}l->length-=1;}//打印所有元素测试⽤void show(struct list l){for (int i = 0; i < l.length; ++i) {printf("%d\n",l.data[i]);}}//测试int main() {struct list alist = {};insert(&alist,100,alist.length+1);insert(&alist,200,alist.length+1);insert(&alist,300,alist.length+1);insert(&alist,400,alist.length+1);delete(&alist,1);printf("%d\n",alist.length);show(alist);printf("%d\n",get(&alist,4));printf("%d\n", locate(&alist,300));printf("%d\n", get(&alist,1));return 0;}插⼊算法分析:假设线性表中含有n个元素,在插⼊元素时,有n+1个位置可以插⼊,因为要保证数据是连续的每个位置插⼊数据的概率是: 1/(n+1)在i的位置插⼊时,要移动的元素个数为:n - i + 1算法时间复杂度为:O(n)删除算法分析:假设线性表中含有n个元素,在删除元素时,有n个位置可以删除每个位置插⼊数据的概率是: 1/n在i的位置删除时,要移动的元素个数为:n - i算法时间复杂度为:O(n)插⼊与删除的不⾜顺序表在进⾏插⼊和删除操作时,平均要移动⼤约⼀半的数据元素,当存储的数据量⾮常⼤的时候,这⼀点需要特别注意;简单的说,顺序表在插⼊和删除时的效率是不够好的;特别在数据量⼤的情况下;顺序表总结:1.顺序表是⼀维数组实现的线性表2.逻辑上相邻的元素,在存储结构中也是相邻的3.顺序表可实现随机读取优缺点:优点:⽆需为了表⽰元素直接的逻辑关系⽽增加额外的存储空间可⽅便的随机存取表中的任⼀节点缺点:插⼊和删除运算不⽅便,需要移动⼤量的节点顺序表要求占⽤连续的存储空间,必须预先分配内存,因此当表中长度变化较⼤时,难以确定合适的存储空间⼤⼩;顺序表节点存储地址计算:设第i个节点的存储地址为x设顺序表起始地址为loc,每个数据元素占L个存储单位计算公式为:x = loc + L * (i-1)如 loc = 100 i = 5 L = 4 则 x = 116线性表的链接存储实现线性表也可通过链接存储⽅式来实现,⽤链接存储⽅式实现的线性表也称为链表 Link List链式存储结构:1.可⽤任意⼀组存储单元来存储数据2.链表中节点的逻辑次序与物理次序不⼀定相同3.每个节点必须存储其后继节点的地址信息(指针)图⽰:单链表单链表指的是只能沿⼀个⽅向查找数据的链表,如上图每个节点由两个部分(也称为域)组成data域存放节点值得数据域next域存放节点的直接后继的地址的指针域(也称为链域)节点结构:每个节点只知道⾃⼰后⾯⼀个节点却不知道⾃⼰前⾯的节点所以称为单链表图⽰:带有head节点的单链表:单链表的第⼀个节点通常不存储数据,称为头指针,使⽤头指针来存储该节点的地址信息,之所以这么设计是为了⽅便运算;单链表特点:其实节点也称为⾸节点,没有前驱,所以头指针要指向该节点,以保证能够访问到起始节点;头指针可以唯⼀确定⼀个链表,单链表可以使⽤头指针的名称来命名;终端节点也称尾节点,没有后继节点,所以终端节点的next域为NULL;除头结点之外的⼏点称为表结点为⽅便运算,头结点中不存储数据单链表数据结构定义//数据结构定义typedef struct node {struct node *next;int data,length;} Node, *LinkList;/** typedef 是⽤来取别名的* Node 是struct node 的别名* *LinkList 是 struct node *的别名* 后续使⽤就不⽤在写struct关键字了*/运算:初始化⼀个空链表有⼀个头指针和⼀个头结点构成假设已定义指针变量L,使L指向⼀个头结点,并使头结点的next为NULL//时间复杂度 :O(1)LinkList initialLinkList() {// 定义链表的头结点LinkList head;//申请空间head = malloc(sizeof(struct node));//使头结点指向NULLhead->next = NULL;return head;}求表长从头指针开始遍历每个节点知道某个节点next为NULL为⽌,next不为空则个数len+1;//求表长时间复杂度 :O(n)int length(LinkList list){int len = 0;Node *c = list->next;while(c != NULL){len+=1;c = c->next;}return len;}读表元素给定⼀个位置n,获取该位置的节点遍历链表,过程中若某节点next为NULL或已遍历个数index=n则结束循环//从链表中获取第position个位置的节点时间复杂度 :O(n)Node *get(LinkList list, int position) {Node *current;int index = 1;current = list->next;//如果下⾯还有值并且还没有到达指定的位置就继续遍历要和查找元素区别开这就是⼀直往后遍历直到位置匹配就⾏了 while (current != NULL && index < position) {current = current->next;index += 1;}if (index == position) {return current;}return NULL;}定位对给定表元素的值，找出这个元素的位置遍历链表,若某节点数据域与要查找的元素data相等则返回当前遍历的次数index//求表head中第⼀个值等于x的结点的序号(从1开始)，若不存在这种结点，返回结果为0 时间复杂度 :O(n)int locate(LinkList list,int data){int index = 1;Node *c;c = list->next;while (c != NULL){if (c->data == data){return index;}index+=1;c = c->next;}return 0;}插⼊在表的第i个数据元素结点之前插⼊⼀个以x为值的新结点new获取第i的节点的直接前驱节点pre(若存在),使new.next = pre.next;pre.next = new;//在表head的第i个数据元素结点之前插⼊⼀个以x为值的新结点时间复杂度 :O(n)void insert(LinkList list, int position, int data) {Node *pre, *new;if (position == 1) {//若插⼊位置为1 则表⽰要插⼊到表的最前⾯即head的后⾯pre = list;} else {//pre表⽰⽬标位置的前⼀个元素所以-1pre = get(list, position - 1);if (pre == NULL) {printf("error:插⼊的位置超出范围");exit(0);}}new = malloc(sizeof(Node));new->data = data;new->next = pre->next;pre->next = new;list->length += 1;}删除删除给定位置的节点获取⽬标节点target的直接前驱节点pre(若pre与⽬标都有效),pre.next = target.next; free(target);//删除链表中第position个位置的节点时间复杂度 :O(n)void delete(LinkList list,int position){//获取要删除节点的直接前驱Node *pre;if (position == 1){ //如要删除的节点是第⼀个那直接前驱就是头结点pre = list;}else{pre = get(list,position-1);}////如果⽬标和前驱都存在则执⾏删除if (pre != NULL && pre->next != NULL){Node *target = pre->next; //要删除的⽬标节点//直接前驱的next指向⽬标的直接后继的nextpre->next = target->next;free(target);printf("info: %d被删除\n",target->data);list->length -= 1;}else{printf("error:删除的位置不正确!");exit(1);}}创建具备指定数据节点的链表//效率⽐较差算法时间复杂度 :O(n^2)LinkList createLinkList1(){LinkList list = initialLinkList();int a;//输⼊的数据int index = 1; //记录当前位置scanf("%d",&a);while (a != -1){ // O(n)insert(list,index++,a); // O(n^2) 每次都要从头遍历链表scanf("%d",&a);}return list;}//尾插算法记录尾节点从⽽避免遍历时间复杂度 :O(n)LinkList createLinkList2(){LinkList list = initialLinkList();int a;//输⼊的数据Node *tail = list;//当前的尾部节点scanf("%d",&a);while (a != -1){ // O(n)Node * newNode = malloc(sizeof(Node)); //新节点newNode->next = NULL;newNode->data = a;tail->next = newNode;//尾部节点的next指向新节点tail = newNode;//新节点作为尾部节点scanf("%d",&a);}return list;}//头插算法每次插到head的后⾯,不⽤遍历但是顺序与插⼊时相反时间复杂度 :O(n)LinkList createLinkList3(){LinkList list = initialLinkList();int a;//输⼊的数据Node * head = list;scanf("%d",&a);while (a != -1){ // O(n)Node * newNode = malloc(sizeof(Node)); //新节点newNode->next = NULL;newNode->data = a;newNode->next = head->next;//将原本head的next 交给新节点;head->next = newNode;//在把新节点作为head的next;scanf("%d",&a);}return list;}优缺点优点:在⾮终端节点插⼊删除时⽆需移动其他元素⽆需预分配空间,⼤⼩没有限制(内存够的情况)缺点:⽆法随机存取读取数据慢链表与顺序表的对⽐:操作顺序表链表读表元O(1)O(n)定位O(n)O(n)插⼊O(n)O(n)删除O(n)O(n)。
