线性表得链式表示和实现

xiaoxiao2021-12-14 21

结点=元素+指针数据域：存储数据元素信息的域。特点：非随机存取。空链表：只存在头结点。基本算法 //int length; //构造一个空的链表 Status InitList(LinkList &L) { //int length; L=(LinkList)malloc(sizeof(LNode)); if(!L) { return OVERFLOW_s;//存储分配失败 } else { L->next=NULL; length = 0; return OK; } } //销毁链表 Status DestroyList (LinkList &L) { free(L); L->next = NULL; return OK; } //清空链表 Status ClearList(LinkList &L) { //int length; L->next = NULL; length = 0; return OK; } //空链表 Status ListEmpty(LinkList L) { if (L->next == NULL) { return OK; } else { return FASLE; } } //创建链表 void CreateList(LinkList &L, int length) { /*int i; LinkList p; L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; for (i = length; i >0; i--) { p = (LinkList)malloc(sizeof(LNode)); cin >> p->data; p->next = L->next; L->next = p; }*/ int i; LinkList p,q; L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; q = L; for (i = 1; i <=length; i++) { p = (LinkList)malloc(sizeof(LNode)); cin >> p->data; q->next = p; q = p; } q->next = NULL; } //链表的长度 Status ListLength(LinkList L) { LinkList p; int i=0; p = L; while (p->next) { p = p->next; i++; } return i; } //获取链表元素 Status GetElem(LinkList L, int i, ElemType &e) { LinkList p; int j = 1; p = L->next; if (i<1 || i>length) { return ERROR; } while (p&&j < i) { p = p->next; j++; } if (!p||j>i) { return ERROR; } else { e = p->data; return OK; } } //置换链表的元素 Status PutElem(LinkList &L, int i, ElemType e) { LinkList p; int j = 1; p = L->next; if (i<1 || i>length) { return ERROR; } while (p&&j < i) { p = p->next; j++; } if (!p||j>i) { return ERROR; } else { p->data = e;; return OK; } } //查找链表中的元素 Status LocateElem(LinkList L, ElemType e) { LinkList p; int j = 0; p = L; while (p->next&&p->data != e) { p = p->next; j++; } if (p->data==e&&j<=length) { return j; } else { return ERROR; } } //查找链表的前驱 Status PriorElem(LinkList L, int cur_e, ElemType &pre_e) { int i=1,j=1; LinkList p,q; //int j = LocateElem(L, cur_e); p = L->next; q = L; /*if (j == 0||j==1) { return ERROR; } else { while (p&&i < j-1) { p = p->next; i++; } pre_e = p->data; return OK; }*/ while (p&&p->data != cur_e) { p = p->next; q = q->next; j++; } if ( j>length||j == 1) { return ERROR; } else { pre_e = q->data; return OK; } } //查找链表的后继 Status NextElem(LinkList L, int cur_e, ElemType &next_e) { int i = 1,j=0; LinkList p,q; //int j = LocateElem(L, cur_e); p = L; q = L->next; /*if (j == 0 || j == length) { return ERROR; } else { while (p&&i < j+1) { p = p->next; i++; } next_e = p->data; return OK; }*/ while (p->next&&p->data != cur_e) { p = p->next; q = q->next; j++; } if (j >= length) { return ERROR; } else { next_e = q->data; return OK; } } //链表中插入元素 Status ListInsert(LinkList &L, int i, ElemType e) { LinkList p,s; int j = 0; p = L; if (i<1 || i>length) { return ERROR; } while (p&&j < i-1) { p = p->next; j++; } if (!p || j>i - 1) { return ERROR; } else { s = (LinkList)malloc(sizeof(LNode)); s->data = e; s->next = p->next; p ->next= s; length++; return OK; } } //链表中删除元素 Status ListDelete(LinkList &L, int i, ElemType &e) { LinkList p, q; int j = 0; p = L; while (p->next&&j < i - 1) { p = p->next; j++; } if (!(p->next) || j>i - 1) { return ERROR; } else { q = p->next; p->next = q->next; e = q->data; free(q); length--; return OK; } } //遍历链表 void ListTraverse(LinkList L) { int i=1; LinkList p; p = L; while (i < length) { p = p->next; i++; cout << p->data << "->"; } cout << p->next->data; cout << endl; }

转载请注明原文地址: https://ju.6miu.com/read-971037.html

专利

最新回复(0)