单链表

浏览量:256    修改时间:2017-07-04 00:12:31
/** * Created on: 2016年10月13日 01:01:54 * Author: Guest * Copyright (c) 2016, tool.usta.wiki , All Rights Reserved. */ // LinkList.cpp : 定义控制台应用程序的入口点。 // 单链表 #include<iostream> #include<malloc.h> using namespace std; typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LinkList; //头插法建表,按原数组倒序排列 void CreateListF(LinkList *&L, ElemType a[], int n) { LinkList *s; L = (LinkList *)malloc(sizeof(LinkList)); //L->data = 0; //表头有一个空的节点 L->next = NULL; //创建头结点,其next域置为NULL for (int i = 0; i < n; i++) { s = (LinkList *)malloc(sizeof(LinkList)); s->data = a[i]; s->next = L->next; //将*s插在原开始节点之前,头结点之后 L->next = s; } } //尾插法建表,按原数组顺序排列 void CreateListR(LinkList *&L, ElemType a[], int n) { LinkList *s, *r; L = (LinkList *)malloc(sizeof(LinkList)); //创建头结点 //L->data = 0; 表头有一个空的节点 r = L; //r始终指向尾节点,一开始指向头结点 for (int i = 0;i < n;i++) { s = (LinkList *)malloc(sizeof(LinkList)); s->data = a[i]; r->next = s; //将*s插入*r之后 r = s; } r->next = NULL; //尾节点next域置为NULL } //输出线性表 void DispList(LinkList *L) { LinkList *p = L->next; while (p != NULL) { cout << " " << p->data << " "; p = p->next; } cout << endl; } //初始化线性表 void InitList(LinkList *&L) { L = (LinkList *)malloc(sizeof(LinkList)); L->next = NULL; } //销毁线性表 void DestroyList(LinkList *&L) { LinkList *pre = L, *p = L->next; while (p != NULL) { free(pre); pre = p; p = pre->next; } free(pre); } //判断线性表是否为空表 bool ListEmpty(LinkList *L) { return (L->next == NULL); } //线性表的长度 //去除线性表头的一个空元素,所以结果是实际长度-1 int ListLength(LinkList * L) { int n = 0; LinkList *p = L->next; while (p != NULL) { n++; p = p->next; } return n; } //求线性表第i个节点的值 int GetElem(LinkList *L, int i) { int j = 0; LinkList *p = L->next; while (j < i&&p != NULL) { j++; p = p->next; } return (p == NULL) ? -1 : p->data; } //按元素值查找其在线性表中的位置 int LocateElem(LinkList *L, ElemType e) { int j = 1; LinkList *p = L->next; while (p!=NULL&&p->data!=e) { j++; p = p->next; } return (p == NULL) ? -1 : j; } //插入数据元素到第i个位置之后 bool ListInsert(LinkList * &L, int i, ElemType e) { int j = 1; LinkList *s, *p=L->next; while (j<i&&p!=NULL){ j++; p = p->next; } if (p != NULL) { s = (LinkList *)malloc(sizeof(LinkList)); s->data = e; s->next = p->next; p->next = s; return true; } return false; } //删除第i个节点 bool ListDelete(LinkList *&L, int i) { int j = 1; LinkList *s, *p = L->next; while (j<i-1&&p != NULL) { j++; p = p->next; } //此时p是需要删除节点的前驱节点 if (p->next != NULL) { s = p->next; p->next = s->next; free(s); return true; } return false; } //设计一个算法,删除一个单链表的最大元素节点 void DelMax(LinkList * &L) { LinkList *p = L->next, *pre = L, *maxp = p, *maxpre = pre; while (p!=NULL) { if (maxp->data < p->data) { maxp = p; maxpre = pre; } pre = p; p = p->next; } maxpre->next = maxp->next; free(maxp); } int main() { int data[] = { 1,5,9,3,5,7 }; LinkList * L; CreateListF(L, data, 6); cout << "头插法建表L:\n"; DispList(L); //cout << L << endl; //cout << &*L << endl; //cout << *&L << endl; // cout << &L << endl; int data2[] = { 1,2,3,4,5,6 }; LinkList *L2; CreateListR(L2, data2, 6); cout << "尾插法建表L2:\n"; DispList(L2); int lenL = ListLength(L); cout << "表L的长度为:" << lenL << endl; int lenL2 = ListLength(L2); cout << "表L2的长度为:" << lenL2 << endl; ElemType L5 = GetElem(L, 5); cout << "线性表L的第五个元素的值是:" << L5 << endl; int j = LocateElem(L, 9); cout << "元素值9在线性表L中的位置是:" << j << endl; ElemType x = 666; bool ins = ListInsert(L2, 5, x); cout << "将元素值666插入到线性表L2的第5个位置,结果是:" << ins << endl; cout << "此时线性表L2为:"; DispList(L2); bool del = ListDelete(L2, 2); cout << "删除线性表L2第2个节点的结果是:" << del << endl; cout << "此时线性表L2为:"; DispList(L2); cout << "删除线性表L最大节点之前是:"; DispList(L); DelMax(L); cout << "删除线性表L最大节点之后是:"; DispList(L); getchar(); return 0; }