[数据结构]单链表

struct Node { ElementType Element; Node* Next; }; typedef struct Node *PtrToNode; typedef PtrToNode List; typedef PtrToNode Position; List CreatList();//创建一个单链表 int IsEmpty(List L);//测试链表是否是空表 int IsLast(Position P,List L);//测试当前位置是否为链表末尾的函数 int Find(ElementType X,List L);//返回某个元素在链表中的位置 Position FindPrevious(ElementType X,List L);//找到数据域为X的节点的前一个节点 void Delete(ElementType X,List L);//删除链表中值为X的节点 void Insert(List L,int i,ElementType X);//在第i个位置之前插入X void push_back(List L,ElementType X);//在链表尾部插入元素X int GetLength(List L);//返回链表的长度 void PrintList(List L);//打印链表 List CreatList(){ List L; L=(PtrToNode)malloc(sizeof(struct Node)); L->Next=NULL; return L; } int IsEmpty(List L) { return L->Next==NULL; } int IsLast(Position P,List L) { return P->Next==NULL; } int Find(ElementType X,List L) { Position P; int i=1; P=L->Next; while(P!=NULL&&P->Element!=X){ P=P->Next; i++; } if(P==NULL){ cout<<"未找到该元素"; return -1; } else return i; } Position FindPrevious(ElementType X,List L) { Position P; P=L; while(P->Next!=NULL&&P->Next->Element!=X) P=P->Next; return P; } void Delete(List L,int i) { Position P=L; Position TmpCell;//创建一个临时结点 int j=0; while(P->Next&&j<i-1){ P=P->Next; ++j; } if(!(P->Next||j>i-1)) return; TmpCell=P->Next; P->Next=TmpCell->Next; free(TmpCell); } void Insert(List L,int i,ElementType X) { Position P=L; Position TmpCell;//临时结点 int j=0; while(P&&j<i-1){ P=P->Next; ++j; } if(!P||j>i-1) return; TmpCell=(Position)malloc(sizeof(struct Node)); TmpCell->Element=X; TmpCell->Next=P->Next; P->Next=TmpCell; } void push_back(List L,ElementType X){ PtrToNode L1=L; while(L1->Next!=NULL){ L1=L1->Next; } Position TmpCell; TmpCell=(Position)malloc(sizeof(struct Node)); TmpCell->Element=X; L1->Next=TmpCell; TmpCell->Next=NULL; } int GetLength(List L){ int res; while(L!=NULL){ res++; L=L->Next; } return res; } void PrintList(List L){ List P=L; while(P!=NULL){ cout<<P->Element<<" "; P=P->Next; } cout<<"\n"; } //测试 /*#include<iostream> #include<stdio.h> #include<stdlib.h> using namespace std; typedef int ElementType; int main(){ List L; L=CreatList(); L->Element=0; int Length,j,f; cout<<"创建一个链表！\n"; cout<<"\n请输入初始链表的长度："; cin>>Length; cout<<"\n请输入链表中要存储的值："; for(int i=0;i<Length;i++){ cin>>j; push_back(L,j); } cout<<"\n当前链表为："; PrintList(L); cout<<"\n在链表第三个位置插入100\n"; Insert(L,3,100); cout<<"\n当前链表为："; PrintList(L); cout<<"\n删除链表的第二个元素\n"; Delete(L,2); cout<<"\n当前链表为："; PrintList(L); cout<<"\n输入要查找的元素："; cin>>f; cout<<"\n元素"<<f<<"的位置为"<<Find(f,L)<<"\n"; cout<<"\n链表的当前长度为："<<GetLength(L)<<"\n"; cout<<"\n0表示链表的头结点"; } */