线性表抽象数据类型ADT一般格式:ADT 抽象数据类型名字{Data 数据对象数据关系:数据类型与对象之间的关系Operation(基本操作)}ADT 类型名赋值参数可以只提供输入值,若加上,怎还将返回操作结果三元组定义ADTTriplet{数据对象:D {e1,e2,e3|e1,e2,e3∈\in∈ElemSet(某个关系运算的集合)}数据关系:R {e1,e2,e2,e3}基本操作:InitTriplet(T,v1,v2,v3)构造三元组,给三个元素赋值V1-V3DestroyTriplet(T)三元组T被销毁Put(T,i,e)三元组已存在下,改变第i个元素为eGet(T,i,e)三元组已存在时,用E返回第I个元素的值IsAscending(T)三元组已存在,判断是否升序排列IsDescending(T)三元组已存在,判断是否是降序排列Max(T,e)三元组已存在,把E改为三个元素的最大值Min(T,e)返回三个元素的最小值}ADTTriplet线性表除去首个与末尾数据,有且仅有一个前驱,一个后延的数据类型是一组数据类型相同的元素的有限序列操作初始化插入访问删除增长缩短抽象数据类型线性表定义ADT list { 数据对象:D {a | a ElemSet , i 1,2,3...} 数据关系:R1 {ai-1, ai | ai-1, ai D, i 2,...,n} 基本操作: InitList(L) \\初始化 DestroyList(L) \\销毁空表 ClearList(L) \\置为空表 ListEmpty(L) \\判断是否为空表 ListLength(L) \\返回数据元素个数 GetElem(L,i,e) \\获取I位置的数据,用E输出 LocateElem(L,e,compare()) \\ PriorLem(L,cur_e,pre_e) \\若cur_e不是第一个元素,则pre_E返回前驱,否则操作失败 NextElem(L,cur_e,next_e) \\同上,返回后继 ListInsert(L,i,e) \\在第I个元素之前插入元素E ListDelete(L,i,e) \\删除第i个元素,并且用e返回删除的元素的值 ListTraverse(L,visit()) \\遍历线性表 }链表算法快慢指针:(针对寻找倒数K个值)/* 任务描述: 一个链表只给出了头指针list,在不改变链表的情况下,找到倒数k(正整数)的节点的值 成功找到输出1,并返回data域的值,未成功找到则返回零*/设置两个指针,例如要找到倒数第K个节点,则先让快指针先走K步,随后两个指针一起向后移动,直到快指针 指向空值,则慢指针就指向了要找的值int findNodeFS(Link* head,int k) { Link* fast head-next; Link* slow head-next; for(int i 0; ik; i) { fast fast-next; } while(fast ! NULL) { fast fast - next; slow slow- next; } ElemType a slow - data; return a; }空间换时间/*用单链表保存N个整数,要求是把所有绝对值相同的整数只保留第一个 EG.1-2--1-56-1-1--1.处理后为1-2-56.尽量时间复杂度高效*/ //思路,就是找一个数组,数组的长度对应链表中最大数字的值, //初始情况下数组全部为0,但是遍历链表时,每遇到一个数字就把对应下标的数组中数字的值变为一 //此后每次遇到数字时先检查对应下标的值为1/0,若为1就直接删除,若为0就保留反转链表/* 利用三个辅助指针,一小部分一小部分逐段反转,直到second指针指向NULL,把third变成头指针 */int ReverseList(Node *head) { Node* first NULL; Node* second head-next; Node* third; while(second ! NULL) { third second-next; second-next first; //这一步就是反转 first second; second third; } Node* hd InitList(); hd-next first; return hd; }循环链表单向循环链表:最后一个结点的指针域指向头节点,整个形成一个环状结构判别条件就是 p-next!L,而不是NULL双向链表在单向链表中,寻找直接后继的时间复杂度为O(1),但寻找直接前驱的复杂度为O(n)在双向链表中,有两个指针域,一个指向直接后继,另一个指向直接前驱1.节点定义typedefintElemType;typedefstructnode{ElemType data;structnode*prev,*next;//一个指向前驱,另一个后继}Node;基础算法1.插入//头插法//先建立新节点,新节点的prev指向头结点的后继,next指向第一个节点的前驱,然后第一个节点的prev指向Node*insertHead(Node*L,ElemType e){Node*p(Node*)malloc(sizeof(Node));p-datae;p-prevL;p-nextL-next;if(L-next!NULL){L-next-prevp;}L-nextp;return1;}尾部插入//尾插法 //新节点的前驱指向尾节点,尾节点的后继指向新节点,新节点的后继是NULL, //新节点赋值为要插入的值 Node* insertTail(Node* tail, ElemType e){ Node* p (Node*)malloc(sizeof(Node)); p-data e; p-prev tail; tail-next p; p-next NULL; return p; }指定位置插入逻辑上和头插法有类似之处void insertNode(Node* L,int pos, ElemType e)//pos是要插入的位置,最终会插入到pos之前 { Node* p L; //需要先找到要插入位置的前驱,剩下的操作逻辑和头插法一样 int i 0; while(i pos -1) { p p-next; i; if(p NULL) { return 0; } } Node* q (Node*)malloc(sizeof(Node)); q-data e; q-prev p; q-next p-next; if(p-next! NULL) {p-next-prev q;} p-next q; }2.删除节点/*先找到要删除节点的前驱,设置节点记录要删除的节点.然后前驱节点的后继指向节点的后继,节点的后继的前驱指向前驱; 注意冗余,当节点为null时候,返回0,代表无法删除 */ int deleteNode(Node* L, int pos) { Node* temp L; int i 0; while(i pos -1) { temp temp-next; i; if(tempNULL) { return 0; } } if(temp-next NULL) { printf(error\n); return 0; } Node* q temp-next; temp-next q-next; q-next-prev temp; free(q); return 1; }