考研 数据结构，考研数据结构真题
2.1 线性表概述
线性表是具有相同数据类型的n个数据元素的有限序列。除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。
注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构。两者属于不同层面的概念，因此不要混淆。
2.2 线性表的顺序表示和实现
概念
线性表的顺序存储又称为顺序表。它是用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。
顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。
顺序表最主要的特点是随机访问（随机存取），即通过首地址和元素序号可以在O(1)的时间内找到指定的元素。但插入和删除操作需要移动大量元素。
顺序表的存储密度高，每个结点只存储数据元素。
顺序表插入操作
最好情况：在表尾插入，元素后移语句不执行，时间复杂度为O(1)
最坏情况：在表头插入，元素后移语句将执行n次，时间复杂度为O(n)
平均情况：平均时间复杂度为O(n)
顺序表删除操作
最好情况：删除表尾元素，无需移动元素，时间复杂度为O(1)
最坏情况：删除表头元素，需要移动除第一个元素外的所有元素，时间复杂度为O(n)
平均情况：平均时间复杂度为O(n)
顺序表按值查找（顺序查找）
最好情况：查找的元素就在表头，仅需比较一次，时间复杂度为O(1)
最坏情况：查找的元素在表尾或不存在时，需要比较n次，时间复杂度为O(n)
平均情况：平均时间复杂度为O(n)
2.3 线性表的链式表示和实现
概念
链式存储线性表时，不需要使用地址连续的存储单元，即它不要求逻辑上相邻的两个元素在物理位置上也相邻，对线性表的插入和删除不需要移动元素，只需要修改指针。
单链表是非随机存储的存储结构，即不能直接找到表中某个特定的结点。
头结点和头指针的区分：不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点链表中的第一个结点，结点内通常不存储信息。
采用头插法建立单链表
从一个空表开始，生成新结点，并将读取到的数据存放在新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。读入数据的顺序与生成的链表中元素的顺序是相反的。每个结点插入的时间为O(1)，设单链表长为n，则总的时间复杂度为O(n)。
采用尾插法建立单链表
将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。时间复杂度为O(n)。
按序号查找结点值
在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域NULL。
时间复杂度为O(n)。
按值查找表结点
从单链表第一个结点出发，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的指针，否则返回NULL。
时间复杂度为O(n)。
插入结点操作
先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i-1个结点，再在其后插入新结点。
主要的时间开销在于查找第i-1个元素，时间复杂度为O(n)。若是在给定的结点后面插入新结点，则时间复杂度仅为O(1)。
删除结点操作
先检查删除位置的合法性，然后找到待删除位置的前驱结点，即第i-1个结点，再将其删除。时间复杂度为O(n)。
双链表
双链表结点中有两个指针prior和next，分别指向其前驱结点和后继结点。双链表中执行按值查找和按位查找的操作和单链表相同，但双链表插入、删除操作的时间复杂度仅为O(1)。
循环单链表
循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环。故表中没有指针域为NULL的结点。
循环双链表 L中，某结点*p为尾结点时，p->next=L；当循环双链表为空表时，其头结点的prior域和next域都等于L。
2.4 静态链表
静态链表是借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next，这里的指针是结点的相对地址（数组下标），又称为游标。
2.5 顺序表和链表的比较
1. 存取方式：顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。
2. 逻辑结构与物理结构：采用顺序存储时，逻辑上相邻的元素，其对应的物理存储位置也相邻。而采用链式存储时，逻辑上相邻的元素，其物理存储位置则不一定相邻。
3. 查找、插入和删除操作：对于按值查找，当顺序表在无序的情况下，两者的时间复杂度均为O(n)；而当顺序表有序时，可采用折半查找，时间复杂度为O(logn)。对于按序号查找，顺序表支持随机访问，时间复杂度仅为O(1)，而链表的平均时间复杂度为O(n)。链表插入、删除较优，只需修改相关结点的指针域即可。
4. 空间分配：链式存储的结点空间只在需要的时候申请分配。
通常较稳定的线性表选择顺序存储，而频繁做插入、删除操作的线性表（即动态性较强）宜选择链式存储。
2.6 线性表的基本运算
顺序表的运算
#include <stdio.h>#include <stdlib.h>#define Size 5typedef struct { int* head; //定义一个名为head的长度不确定的数组，也叫“动态数组” int length; //记录当前顺序表的长度 int size; //记录顺序表的存储容量}Table;//创建顺序表void initTable(Table* t) { //构造一个空的顺序表，动态申请存储空间 t->head = (int*)malloc(Size * sizeof(int)); //如果申请失败，作出提示并直接退出程序 if (!t->head) { printf("初始化失败"); exit(0); } //空表的长度初始化为0 t->length = 0; //空表的初始存储空间为Size t->size = Size;}//插入函数，其中，elem为插入的元素，add为插入到顺序表的位置void insertTable(Table* t, int elem, int add){ int i; //如果插入元素位置比整张表的长度+1还大（如果相等，是尾随的情况），或者插入的位置本身不存在，程序作为提示并自动退出 if (add > t->length + 1 || add < 1) { printf("插入位置有问题\n"); return; } //做插入操作时，首先需要看顺序表是否有多余的存储空间提供给插入的元素，如果没有，需要申请 if (t->length == t->size) { t->head = (int*)realloc(t->head, (t->size + 1) * sizeof(int)); if (!t->head) { printf("存储分配失败\n"); return; } t->size += 1; } //插入操作，需要将自插入位置之后的所有元素全部后移一位 for (i = t->length - 1; i >= add - 1; i--) { t->head[i + 1] = t->head[i]; } //后移完成后，直接插入元素 t->head[add - 1] = elem; t->length++;}//删除函数void delTable(Table* t, int add) { int i; if (add > t->length || add < 1) { printf("被删除元素的位置有误\n"); return; } //删除操作 for (i = add; i < t->length; i++) { t->head[i - 1] = t->head[i]; } t->length--;}//查找函数int selectTable(Table t, int elem) { int i; for (i = 0; i < t.length; i++) { if (t.head[i] == elem) { return i + 1; } } return -1;}//更改函数void amendTable(Table* t, int elem, int newElem) { int add = selectTable(*t, elem); if (add == -1) { printf("顺序表中没有找到目标元素\n"); return; } t->head[add - 1] = newElem;}//输出顺序表中的元素void displayTable(Table t) { int i; for (i = 0; i < t.length; i++) { printf("%d ", t.head[i]); } printf("\n");}int main() { int i,add; Table t = { NULL,0,0 }; initTable(&t); for (i = 1; i <= Size; i++) { t.head[i - 1] = i; t.length++; } printf("原顺序表：\n"); displayTable(t); printf("删除元素1:\n"); delTable(&t, 1); displayTable(t); printf("在第2的位置插入元素5:\n"); insertTable(&t, 5, 2); displayTable(t); printf("查找元素3的位置:\n"); add = selectTable(t, 3); printf("%d\n", add); printf("将元素3改为6:\n"); amendTable(&t, 3, 6); displayTable(t); return 0;}
运行结果如下：
链表的基本运算
#include <stdio.h>#include <stdlib.h>//链表中节点的结构typedef struct link { int elem; struct link* next;}Link;Link* initLink() { int i; //1、创建头指针 Link* p = NULL; //2、创建头结点 Link* temp = (Link*)malloc(sizeof(Link)); temp->elem = 0; temp->next = NULL; //头指针指向头结点 p = temp; //3、每创建一个结点，都令其直接前驱结点的指针指向它 for (i = 1; i < 5; i++) { //创建一个结点 Link* a = (Link*)malloc(sizeof(Link)); a->elem = i; a->next = NULL; //每次 temp 指向的结点就是 a 的直接前驱结点 temp->next = a; //temp指向下一个结点（也就是a),为下次添加结点做准备 temp = temp->next; } return p;}//p为链表，elem为目标元素，add为要插入的位置void insertElem(Link* p, int elem, int add) { int i; Link* c = NULL; Link* temp = p;//创建临时结点temp //首先找到要插入位置的上一个结点 for (i = 1; i < add; i++) { temp = temp->next; if (temp == NULL) { printf("插入位置无效\n"); return; } } //创建插入结点c c = (Link*)malloc(sizeof(Link)); c->elem = elem; //① 将新结点的 next 指针指向插入位置后的结点 c->next = temp->next; //② 将插入位置前结点的 next 指针指向插入结点； temp->next = c;}//p为原链表，elem 为要删除的目标元素int delElem(Link* p, int elem) { Link* del = NULL, *temp = p; int find = 0; //1、找到目标元素的直接前驱结点 while (temp->next) { if (temp->next->elem == elem) { find = 1; break; } temp = temp->next; } if (find == 0) { return -1;//删除失败 } else { //标记要删除的结点 del = temp->next; //2、将目标结点从链表上摘除 temp->next = temp->next->next; //3、释放目标结点 free(del); return 1; }}//p为原链表，elem表示被查找元素int selectElem(Link* p, int elem) { int i = 1; //带头结点，p 指向首元结点 p = p->next; while (p) { if (p->elem == elem) { return i; } p = p->next; i++; } return -1;//返回-1，表示未找到}//p 为有头结点的链表，oldElem 为旧元素，newElem 为新元素int amendElem(Link* p, int oldElem, int newElem) { p = p->next; while (p) { if (p->elem == oldElem) { p->elem = newElem; return 1; } p = p->next; } return -1;}//输出链表中各个结点的元素void display(Link* p) { p = p->next; while (p) { printf("%d ", p->elem); p = p->next; } printf("\n");}//释放链表void Link_free(Link* p) { Link* fr = NULL; while (p->next) { fr = p->next; p->next = p->next->next; free(fr); } free(p);}int main() { Link* p = initLink(); printf("初始化链表为：\n"); display(p); printf("在第 3 的位置上添加元素 6：\n"); insertElem(p, 6, 3); display(p); printf("删除元素4：\n"); delElem(p, 4); display(p); printf("查找元素 2：\n"); printf("元素 2 的位置为：%d\n", selectElem(p, 2)); printf("更改元素 1 的值为 6：\n"); amendElem(p, 1, 6); display(p); Link_free(p); return 0;}
考研 数据结构(考研数据结构参考)
未经允许不得转载：考研培训机构 » 考研 数据结构(考研数据结构参考)
