-
链表ADT实现
2016-08-16 22:29:03每个结构含有表元素和指向包含该元素后继的结构的指针。除了头节点,每一个结点都有唯一的前继。除最后一个结点,每一个结点都有一个后继。 插入: 删除: 双向链表 双向链表与...链表的定义:
链表链表有一系列不必再内存中连续的结构组成,不需要使用地址连续的存储单元。它是通过“链”来建立逻辑关系的,因此在对链表进行插入,删除操作时不需要移动元素,而只需要修改指针即可。链表分类:按是否包含指向前继的指针可分为单链表和双向链表;按是否成环状可以分为循环链表和非循环链表。
由于连表示离散的分布在存储空间的,因此链表是非随机存取的,只能从某个特定节点开始遍历一次查找。
通常为方便操作,在链表第一个节点前附加一个头节点,头节点的指针与指向链表的第一个元素节点。
链表的实现与常见算法
单链表
每个结构含有表元素和指向包含该元素后继的结构的指针。除了头节点,每一个结点都有唯一的前继。除最后一个结点,每一个结点都有一个后继。
插入:
删除:
双向链表
双向链表与单链表的不同之处在于,双向链表的每个结点含有两个指针域,其中一个指向直接前继,一个指向直接后继。这样双向链表可以沿两个方向进行遍历;插入:删除:struct LNode { ElementType e; PtrToLNode Next; };
typedef struct LNode *PtrToLNode;
typedef PtrToLNode List;
List List_Init(void) { List L = (List)malloc(sizeof(LNode)); L->Next = NULL; return L; } int List_IsEmpty(List L) { if (L->Next = NULL) return 1; else return 0; } void List_Print(List L) { PtrToLNode p = L->Next; while (p){ printf("%d\t", p->e); p = p->Next; } printf("\n"); } void List_Pre_Create(List L)//头插法建立单链表 { ElementType x; scanf("%d", &x); while (x != 9999) { PtrToLNode p = (PtrToLNode)malloc(sizeof(LNode)); p->e = x; p->Next = L->Next; L->Next = p; scanf("%d", &x); } } void List_Post_Create(List L)//尾差法建立单链表 { ElementType x; PtrToLNode p, r = L; scanf("%d", &x); while (x != 9999) { p = (PtrToLNode)malloc(sizeof(LNode)); p->e = x; r->Next = p; r = p; scanf("%d", &x); } r->Next = NULL; } PtrToLNode List_FindPre(List L, PtrToLNode r)//返回结点r的直接前继 { PtrToLNode pre = L, p = pre->Next; while (p != r) { pre = p; p = p->Next; } return pre; } int List_Length(List L)//求链表长度 { int Length = 0; PtrToLNode p = L->Next; while (p) { ++Length; p = p->Next; } return Length; } void List_Insert(List L, Position p, ElementType x)//在结点p处插入新节点 { PtrToLNode pre = List_FindPre(L, p), s; s = (PtrToLNode)malloc(sizeof(LNode)); s->e = x; s->Next = p; pre->Next = s; } PtrToLNode List_FindMid(List L)//返回中间元素结点 { PtrToLNode p, r; p = r = L->Next; while (r->Next != NULL && r->Next->Next != NULL){ p = p->Next; r = r->Next->Next; } printf("%d\n", p->e); return p; } void List_Delete(List L, ElementType x)//删除节点 { PtrToLNode pre = L, p = L->Next, temp; while (p){ if (p->e != x) { pre = p; p = p->Next; } else{ temp = p->Next; pre->Next = temp; free(p); p = temp; } } } void List_DeleteRepeat(List L)//删除有序链表中重复元素的结点 { PtrToLNode pre = L->Next, p = pre->Next, temp; while (p){ if (pre->e == p->e) { temp = p->Next; pre->Next = temp; free(p); p = temp; } else { pre = p; p = p->Next; } } } PtrToLNode List_Last_K(List L, int k)//返回倒数第K个结点 { PtrToLNode p, r; p = r = L; if (k > List_Length(L)) { printf("The k is Bigger Than L's Length!\n"); return NULL; } for (int i = 0; i < k; ++i) r = r->Next; while (r){ r = r->Next; p = p->Next; } printf("%d\n", p->e); return p; } /*若两单链表有公共结点,则从起始公共结点至尾结点两者均相同,因此将两链表尾部对齐,开始比较第一个相同结点即为起始公共结点*/ PtrToLNode List_CommonNode(List L1, List L2)//返回两单链表的公共起始节点 { int Length1, Length2, dist; PtrToLNode longlist, shortlist; Length1 = List_Length(L1); Length2 = List_Length(L2); if (Length1 > Length2) { longlist = L1->Next; shortlist = L2->Next; dist = Length1 - Length2; } else { longlist = L2->Next; shortlist = L1->Next; dist = Length2 - Length1; } while (dist--) longlist = longlist->Next; while(longlist && longlist->e != shortlist->e){ longlist = longlist->Next; shortlist = shortlist->Next; } PtrToLNode p = longlist; while (p) { printf("%d\n", p->e); p = p->Next; } return longlist; } void List_Reverse(List L)// { PtrToLNode pre, p, r; pre = L; p = pre->Next; r = p->Next; p->Next = NULL;//将逆置后的p将成为尾结点,将其指针域置空 while (r) { pre = p; p = r; r = r->Next;//遍历链表 p->Next = pre;//逆置 } L->Next = p;//p结点将成为你逆置后的第一个节点,将头节点指向该节点 }
</pre><pre name="code" class="cpp"><pre name="code" class="cpp">void List_Reverse1(List L)//利用头插法逆置链表 { PtrToLNode p, r; p = L->Next; L->Next = NULL; while (p) { r = p->Next; p->Next = L->Next; L->Next = p; p = r; } }
List List_Reverse1(List L, int m, int n)//逆置第m个结点至第n个结点结点 { List prefirst, first, p, r; prefirst = L; first = p = L->Next; for (int i = 1; i != m; ++i) { prefirst = p; p = p->Next; }//prefirst指向第m-1个结点 first = p;//first指向第m个结点 for (int i = m; i <= n; ++i) { r = p->Next; p->Next = prefirst->Next; prefirst->Next = p; p = r; }//利用头插法将m至n结点逆置 first->Next = p;//将first的指针域指向第n+1个结点 return L; }
双链表
-
顺序表ADT实现(带注释)
2017-10-06 13:40:06/* * Created by Dev-c++5.11 ...* @description: 顺序表操作 */#include <stdio.h> #include <stdlib.h> /*函数状态码*/ #define TRUE 1 //成功 #define OK 1 #define FALSE 0 //失败 #d/* * Created by Dev-c++5.11 * @author: Teresa0312 * @date: 2017-10-05 * @description: 顺序表操作 */ #include <stdio.h> #include <stdlib.h> /*函数状态码*/ #define TRUE 1 //成功 #define OK 1 #define FALSE 0 //失败 #define ERROR 0 //错误 #define INFEASIBLE -1 //不可行的 #define OVERFLOW -2 //溢出 #define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 #define LISTINCREMENT 10 //线性表存储空间的增量 typedef int ElemType; //基本数据类型 typedef int Status; //函数的返回值类型 /*线性表的动态分配顺序存储结构*/ typedef struct{ ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量 以sizeof(ElemType)为单位 }SqList; //初始化线性表L Status ListInit(SqList *L){ L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)); //分配LIST_INIT_SIZE个ElemType的空间 if (!L->elem){ exit(OVERFLOW); //存储分配失败则退出程序 } L->length = 0; //空表长度为0 L->listsize = LIST_INIT_SIZE; //初试存储容量 return TRUE; } //销毁线性表L Status DestroyList(SqList *L){ free(L->elem); //先释放内存 L->elem = NULL; //再赋值为NULL L->length = 0; L->listsize = 0; return OK; }; //将L置为空表 Status ClearList(SqList *L){ L->length = 0; //置为空表长度为0 return OK; } //若L为空表则返回TRUE 否则返回 FALSE Status ListEmpty(SqList L){ if (L.length == 0) return TRUE; else return FALSE; } //返回L中数据元素的个数 Status ListLength(SqList L){ return L.length; } //用e返回L中第i个数据元素的值 Status GetElem(SqList L, int i, ElemType * e){ if (i <= L.length){ //如果i小于线性表的长度 *e = *(L.elem + i - 1); //返回第i个数据元素的值 return *e; } else //否则 返回FALSE return FALSE; } //返回 L中第一个与e满足关系compare()的数据元素的位序 若不存在 则返回0 Status LocateElem(SqList L, ElemType e, Status (*compare)(ElemType,ElemType)){ ElemType *p=&e; int i=0; while (i <= L.length && !(*compare)(*p,e)){ //当i小于等于线性表的长度 并且 没有找到与e满足compare()关系的数据元素时 执行循环 i++; p+=sizeof(ElemType); } if (i < L.length){ //当i小于线性表的长度时 说明找到了 return *p; } else return FALSE; //否则 没有找到 } //若cur_e是L的数据元素 且不是第一个 则用pre_e返回它的前驱 否则操作失败 pre_e无定义 Status PriorElem(SqList L, ElemType cur_e, ElemType * pre_e){ ElemType *p=L.elem; int i = 1; if (*p == cur_e){ //如果是第一个数据元素 则不可行 printf("它没有前驱 不可行"); return INFEASIBLE; } else{ while (i < L.length && *p != cur_e){ //从第一个元素开始 与cur_e比较 直至相等或L的最后 i++; p++; } if (i > L.length) //没找到 返回INFEASIBLE return INFEASIBLE; else{ *pre_e = *(p - 1); //若找到 将后一个元素赋给pre_e return OK; } } } ///若cur_e是L的数据元素 且不是最后一个 则用next_e返回它的前驱 否则操作失败 next_e无定义 Status NextElem(SqList L, ElemType cur_e, ElemType * next_e){ ElemType *p = L.elem; int i = 1; while (i <= L.length && *p != cur_e){ //从第一个元素开始 与cur_e比较 直至相等或L的最后 i++; p++; } if (i >= L.length) //没找到 返回INFEASIBLE return INFEASIBLE; else{ *next_e = *(p + 1); //若找到 将后一个元素赋给next_e return OK; } } //在L中的第i个位置之前插入新的数据元素e,L的长度加1 Status ListInsert(SqList *L, int i, ElemType e){ ElemType *newbase, *q, *p; if (i <1 || i>L->length + 1) //判断i是否在顺序表的长度之内 return FALSE; if (L->length >= L->listsize) { ///如果L.length已经达到或超出设定值,需要扩容 newbase = (ElemType *)realloc(L->elem, (L->listsize + LISTINCREMENT) *sizeof(ElemType)); //重新分配空间 给newbase动态分配一个长度为LISTINCREMENT的新空间d if (!newbase) exit(OVERFLOW); //如果分配失败 返回错误 L->elem = newbase; //新基址 L->listsize += LISTINCREMENT; //增加存储容量 } q = L->elem + i - 1; //q为插入位置 for (p = (*L).elem + (*L).length - 1; p >= q; --p) //插入位置及之后的元素右移 *(p + 1) = *p; //将原来顺序表最后一个位置数据的地址分配给p,然后从后往前依次将数据向后移动一位 *q = e; //插入e (*L).length++; // 表长增1 return OK; } //删除L中的第i个元素 并用e返回其值 L的长度减1 Status ListDelete(SqList *L, int i, ElemType * e){ ElemType *q, *p; if (i <1 || i>L->length) //判断i是否在顺序表的长度之内 return ERROR; p = L->elem + L->length - 1; //p指向最后一个数据元素 q = L->elem + i - 1; //q为删除位置 for (q; q < p; q++) //删除位置及之后的元素左移 *q = *(q + 1); --(*L).length; // 表长减1 return OK; } //对L的每一个元素调用函数visit 一旦visit()失败 则操作失败 Status ListTraverse(SqList L, void (*visit)(ElemType *)){ ElemType *ptr; //遍历数组 ptr = L.elem; ElemType i = 0; for (i = 0; i < L.length; i++) visit(ptr + i); //遍历数组 printf("\n"); return OK; } //若数据元素a与b相等则返回TRUE 否则返回 FALSE Status compare(ElemType a, ElemType b){ if (a == b){ return TRUE; } else return FALSE; } //输出数据元素 void visit(ElemType *e){ printf("%c ", *e); } int main(){ SqList a; ElemType e; int i = 0; ListInit(&a); printf("顺序表创建成功\n"); for (i = 1; i <=26; i++) ListInsert(&a, i, 97+i-1); printf("初始化顺序表完成\n"); printf("输出顺序表\n"); ListTraverse(a, visit); printf("输出第3个元素的前驱"); PriorElem(a, 'c', &e); printf("%c\n",e); printf("输出第3个元素的后继"); NextElem(a, 'c', &e); printf("%c\n",e); printf("输出与t相等的元素"); printf("%d\n",LocateElem(a,'t',compare)); if(ListDelete(&a,6,&e)) printf("删除%c成功\n",'a'+6-1); printf("输出顺序表\n"); ListTraverse(a, visit); }
-
链表ADT实现(C语言)2018.3.11
2018-03-11 19:23:47/**测试ADT */ int main() { LinkList p=Init_LL(); Insert_LL(p,1,6); Insert_LL(p,2,8); Insert_LL(p,3,4); Insert_LL(p,3,3); Insert_LL(p,2,1); Insert_LL(p,4,9); Printf_LL(p); LinkList q=Init_LL()...#include <stdio.h> #include <stdlib.h> #define name_to_str(name_) (#name_) /**< 定义结点及结构体指针,结构体指针linklist为链表头结点指针*/ typedef struct LNode{ int data; struct LNode* next; }LNode,*LinkList;//结构体指针 /**< 初始化链表 */ LNode* Init_LL() { LinkList p=(LNode*)malloc(sizeof(LNode)); p->data=NULL; p->next=NULL; return p; } /**< 在第pos个结点之前插入一个DATA为Val的新节点 */ void Insert_LL(LinkList pLL,int pos,int Val) { LNode* P=pLL; LNode* A=Init_LL();//不初始化结点不能使用,malloc相关。 A->data=Val; int i; for(i=0;i<pos-1;i++) {if(P) P=P->next; else { printf("位置非法"); exit(-1);} } A->next=P->next; P->next=A; } /**< 删除结点,pos之前 */ void Delete_LL(LinkList pLL,int pos) { int i; LinkList q,p=pLL; for(i=0;i<pos-1;i++) p=p->next; q=p->next; p->next=q->next; free(q); } /**< 求直接前驱 */ LNode* PriorElment_LL(LinkList pLL,int Data) { LinkList p=pLL; while(p->next->data!=Data) p=p->next; printf("%d_prior_element_data_is_%d",Data,p->data); return p; } /**< 求直接后继 */ LNode* NextElment_LL(LinkList pLL,int Data) { LinkList p=pLL; while(p->data!=Data) p=p->next; printf("%d_next_element_data_is_%d",Data,p->data); return p; } /**< 返回第POS个数据的值*/ int GetElement_LL(LinkList pLL,int pos) { LinkList p=pLL; int i; for(i=0;i<pos;i++) p=p->next; printf("the %dth element is %d",pos,p->data); return p->data; } /**< 泡排 */ void BubbleSort_LL(LinkList pLL) { LinkList p=pLL,q; int cnt=0,i,j,temp; while(p->next!=NULL) { cnt++; p=p->next; } //printf("cnt=%d",cnt); q=pLL->next; for(i=0;i<cnt-1;i++) { p=q; for(j=0;j<cnt-i-1;j++) { if(p->data<p->next->data) { temp=p->data; p->data=p->next->data; p->next->data=temp; //printf("比较%d?=%dexchange\n",p->data,p->next->data);///非常奇怪,总是大数小数exchange p=p->next; } else { //printf("比较%d?=%dunchange\n",p->data,p->next->data); p=p->next;} } //printf("当前循环完成\n"); } Printf_LL(pLL); } /**< 合并有序链表 */ LinkList Add_LL(LinkList p,LinkList q) { LinkList a=p->next,b=q->next; LinkList c=Init_LL(); LinkList L=c; while(a&&b) { if (a->data>=b->data) { // printf("1 %d,%d\n",a->data,b->data); c->next=a; a=a->next; } else { // printf("2 %d,%d\n",a->data,b->data); c->next=b; b=b->next; } // printf("CDATA=%d\n",c->data); c=c->next; c->next=NULL; } if (a==NULL) c->next=b; else c->next=a; printf("合并有序链表结果为:\n"); Printf_LL(L); } /**< 打印链表 */ void Printf_LL(LinkList pLL) { LNode* p=pLL; int i=1; printf("打印链表结果为:"); do{ p=p->next; printf("linklist[%d]=%d\t",i,p->data); i++; }while(p->next!=NULL); printf("\n\n"); } /**< 测试ADT */ int main() { LinkList p=Init_LL(); Insert_LL(p,1,6); Insert_LL(p,2,8); Insert_LL(p,3,4); Insert_LL(p,3,3); Insert_LL(p,2,1); Insert_LL(p,4,9); Printf_LL(p); LinkList q=Init_LL(); Insert_LL(q,1,2); Insert_LL(q,2,5); Insert_LL(q,3,7); Insert_LL(q,3,3); Insert_LL(q,2,11); Insert_LL(q,3,20); Insert_LL(q,1,12); Printf_LL(q); BubbleSort_LL(p); BubbleSort_LL(q); Add_LL(p,q); return 0; }
-
链表ADT C语言实现
2016-01-25 18:34:26链表ADT 自己打的单链表 希望代码对大家有帮助哈哈,很全。 基本实现了应该有的功能 1.判断链表是否为空 2.判断链表是否为满 3.节点数量 4.链表的遍历 5.链表节点的替换 6.链表节点的寻找 7.链表节点的插入 8.链表...链表ADT
自己打的单链表
希望代码对大家有帮助哈哈,很全。
基本实现了应该有的功能
1.判断链表是否为空
2.判断链表是否为满
3.节点数量
4.链表的遍历
5.链表节点的替换
6.链表节点的寻找
7.链表节点的插入
8.链表节点的添加
#define true 1 #define false 0 #include <stdio.h> #include <stdlib.h> struct list {int data; struct list * next; }; typedef struct list List; int ListIsEmpty( List * head); unsigned int ListItemCount( List * head); void Traverse( List * head); void Replace( List **ptr,int a,List * target); List * SeekItem( List * head,int a); bool InsertItem( List *head,int a,List * target); int InsertHeadItem(List ** ptr,List * target); List * AddItem( List * head); int main(void) { } int ListIsEmpty( List * head) { if(head==NULL) return true; else return false; } unsigned int ListItemCount( List * head) { unsigned int count=0; List * p=head; while(p!=NULL){ ++count; p=p->next; } return count; } void Traverse( List * head) { int count = 0; List * p=head; while(p!=NULL){ ++count; printf("%d%10d\n",count,p->data); p=p->next; } } void Replace( List **ptr,int a,List * target)//Replace(ptr,a,target);List **ptr 为了能替换第一个节点 ,需要改变头指针的值 { List * p=*ptr; List * pr=p; if(*ptr==NULL) { printf("nothing!"); exit(0); } while(p!=NULL&&p->data!=a){ pr=p; p=p->next; } if(p==NULL){ printf("not found!"); exit(1); } if(p!=NULL){ if(*ptr==p){ target->next=p->next; *ptr=target; free(p); } else{ target->next=p->next; pr->next=target; free(p); } } } List * SeekItem( List * head,int a) { int count=0; List * p,* pr; p=head; pr=p; if(head==NULL){ printf("nothing!"); exit(0); } while(p!=NULL){ count++; pr=p; if(p->data==a){ printf("find it , it's %d\n",count); return p; } p=p->next; } if(p=NULL){ printf("not found!"); return NULL; } } bool InsertItem( List * head,int a,List * target) { List * p; p=SeekItem(head,a); if(p==NULL){ printf("not found !"); return false; } target->next=p->next; p->next=target; return true; } int InsertHeadItem(List ** ptr,List * target) { target->next=*ptr; *ptr=target; return true; } List *AddItem( List * head) { List * pr=head; List * p=NULL; p=(List *)malloc(sizeof(List)); if(p==NULL){ printf("can't' malloc!"); } p->next=NULL; printf("please input data :"); scanf("%d",&p->data); if(head==NULL){ head=p; } else{ while(pr->next!=NULL){ pr=pr->next; printf("text!\n"); } pr->next=p; } Traverse(head); return head; }
原创 转载注明出处
-
链表ADT的实现
2015-12-03 19:05:00list.h文件 1 /*链表的类型声明*/ 2 3 typedef int ElementType; 4 5 /* START: fig3_6.txt */ 6 #ifndef _List_H 7 #define _List_H 8 9 struct Node; 10 ... -
链表ADT设计模板的简单应用——链表的ADT的实现C++版
2020-10-17 15:59:04文章目录ADT分析总结LinkList(LinkList &List);分析与总结operator=(LinkList &List) 、ListDestroy()和ClearList()ListDestroy()ListClear()分析与总结ListLength()和ListEmpty()分析与总结InsFirst... -
数据结构:链式表ADT的实现
2019-09-23 19:34:49链表分很多种,有单链表、双链表、循环链表等,这里我以单链表为例,实现单链表的ADT。 单链表是一种最简单的链表表示,也叫作线性链表。用它来表示线性表时,用指针表示节点间的逻辑关系。因此单链表的一个存储... -
Data Structure 初学链表(ADT实现)
2015-08-09 16:37:38通过c语言实现最原始的链表,...①按照ADT的实现,把链表的实现划分为许多功能。#include #include typedef struct LNode{ int elem; struct LNode *next; }LNode, *LinkedList; void IntiList(LinkedList *);//初始 -
表ADT的两种实现
2019-10-28 14:45:04表的简单数组实现 对表的所有操作都可以通过数组来实现,它可以使得printList以线性时间被执行,而findKth操作则花费常数时间,不过,插入和删除的花费却潜藏着昂贵的开销,这取决于插入和删除发生在什么地方。 最坏... -
数据结构:顺序表ADT的实现
2019-09-23 17:56:27下面给出顺序表ADT的C++实现: 一、顺序表的基本操作 1.构造函数 通过指定sz,定义数组的长度。 LinearList::LinearList(int sz){ //构造函数,通过指定size,定义数组长度 if(sz>0){ data = new T... -
数据结构---链表ADT C++实现
2018-10-10 22:47:00最近在学习数据结构,刚开始...现将实现代码发表此地,以备日后复习,若有错误或者建议,欢迎告知本人! 1. 节点类 1 class Node { 2 public: 3 int data; 4 Node *next; 5 Node(int da): 6 data(da), n... -
jsp无限级可分类的分类表ADT的实现
2007-09-26 12:05:00源码下载地址: http://www.javaall.com/resource/news.rar 本文的目的是利用数据结构: 树 ,来实现一个分类表ADT, 这个分类表ADT可以实现无限级分类 本例程采用Structs 架构, 符合MVC设计模式 数据库采用SQL ... -
表ADT
2017-01-02 17:53:26表的简单数组实现 虽然数组是由固定容量创建的,但在需要的时候可以用双倍的容量创建一个不同的数组。它解决由于使用数组而产生的最严重的问题,即为了使用一个数组,需要对表的大小进行估计。而这种估计在Java或...
收藏数
807
精华内容
322