#include <stdio.h> #include <malloc.h> typedef int ElemType; typedef struct _LNode { ElemType nData; struct _LNode* next; }LNode,*pLineList; //创建 pLineList InitList() { pLineList pHead = (pLineList)malloc(sizeof(LNode)); pHead->nData = 0; pHead->next = NULL; return pHead; } //销毁 void DestroyList(pLineList* pList) { free(*pList); *pList = NULL; } //清空 void ClearList(pLineList* pList) { *pList = NULL; } //是否为空 bool ListEmpty(pLineList pList) { if (pList->next == NULL) { return true; } return false; } //长度 int ListLenght(pLineList pList) { pLineList p = pList->next; int nCount = 0; while(p) { nCount++; p = p->next; } return nCount; } //得到第i个值 ElemType GetItem(pLineList pList, int i) { if (pList->next == NULL) //空链表 { return -1; } pLineList p = pList->next; int n = 1; while(p && n<i) { p = p->next; n++; } if (!p || n > i) { return -1; } return pList->nData; } //与e的关系判断 int LocateList(pLineList pList,ElemType e) { if (pList->nData < e) { return -1; } else if (pList->nData == e) { return 0; } return 1; } //返回前驱 LNode PriorList(pLineList pList, ElemType e) { pLineList p= pList; while(p->next) { if (p->next->nData == e) { break; } } return *p; } //返回后继 LNode NextList(pLineList pList, ElemType e) { pLineList p= pList->next; while(p) { if (p->nData == e) { break; } } return *p->next; } //插入 void InsertList(pLineList* pList, int i, ElemType e) { pLineList p = *pList; int n = 1; while(p && n<i) { p = p->next; n++; } if (!p || n > i) { return; } LNode* pNode = (LNode*)malloc(sizeof(LNode)); pNode->nData = e; pNode->next = p->next; p->next = pNode; } //删除 ElemType deleteList(pLineList* pList,int i) { ElemType elem; pLineList p = *pList; int n = 1; while(p->next && n<i) { p = p->next; n++; } if (!p->next || n>i) { return -1; } pLineList q = p->next; p->next = q->next; elem = q->nData; free(q); q= NULL; return elem; } //输出 void PrintList(pLineList pList) { pLineList p = pList->next; while(p) { printf("%d\n",p->nData); p = p->next; } } //合并 void mergeList(pLineList* pList1,pLineList* pList2) { pLineList pList = *pList1; pLineList p = (*pList1)->next; pLineList q = (*pList2)->next; while(p&&q) { if (p->nData < q->nData) { pList->next = p; pList = p; p = p->next; } else { pList->next = q; pList = q; q = q->next; } } pList->next = p?p:q; free(*pList2); *pList2 = NULL; } //倒置 void ReverseList(pLineList* pList) { pLineList pHead = *pList; pLineList p = (*pList)->next; pHead->next = NULL; while(p) { pLineList q = p; p = p->next; q->next = pHead->next; pHead->next = q; } } //查找倒数第k个值 ElemType findK(pLineList pList,int k) { pLineList pk = pList; int n = 0; while(pk && n < k) { n++; pk = pk->next; } if (!pk || n > k) { return -1; } pLineList p = pList; while(pk && p) { p = p->next; pk = pk->next; } return p->nData; } //是否有环 bool isLoop(pLineList pList) { pLineList pShow = pList; pLineList pFast = pList->next; while(pShow && pFast->next) { if (pShow == pFast) { return true; } pShow = pShow->next; pFast = pFast->next->next; } return false; } int main() { pLineList pLine = InitList(); if (ListEmpty(pLine)) { printf("Empty\n"); } else { printf("Not Empty\n"); } InsertList(&pLine,1,6); InsertList(&pLine,1,5); InsertList(&pLine,1,4); InsertList(&pLine,1,3); InsertList(&pLine,1,2); InsertList(&pLine,1,1); deleteList(&pLine,5); pLineList pLine1 = InitList(); if (ListEmpty(pLine1)) { printf("Empty\n"); } else { printf("Not Empty\n"); } InsertList(&pLine1,1,6); InsertList(&pLine1,1,5); InsertList(&pLine1,1,4); InsertList(&pLine1,1,3); InsertList(&pLine1,1,2); InsertList(&pLine1,1,1); mergeList(&pLine,&pLine1); ReverseList(&pLine); printf("%d\n",ListLenght(pLine)); if (isLoop(pLine)) { printf("有环\n"); } else { printf("无环\n"); } PrintList(pLine); printf("%d\n",findK(pLine,3)); DestroyList(&pLine); return 0; }