数据结构：单链表——定义、插入、删除

1、定义

注，以下都是带头节点的单链表

typedef struct LNode { ElementType data; struct LNode *next; }LNode,*LinkList; bool InitList(LinkList &L){ L = (LNode *)malloc(sizeof(LNode)); if(L==NULL){//内存不足 return false; } L->next=NULL; return true; }

这里定义的LNode和 * LinkList实际上是一种表达上的技巧，前者主要强调的是，这是一个结点，而后者则是强调这是一个单链表

判断是否为空

bool IsEmpty(LinkList L){ if(L->next==NULL) return true; else return false; } 2、插入与删除

插入

bool InsertData(LinkList &L,ElementType e,int i){ if(i<1){ printf("插入位置不合法！"); return false; } LNode *p=L; int j=0; while (p!=NULL&&j<i-1) { p=p->next; j++; } if(p==NULL){ printf("插入位置不合法！"); return false; } LNode *temp = (LNode *)malloc(sizeof(LNode)); temp->data=e; temp->next=p->next; p->next=temp; return true; }

删除

bool DeletData(LinkList &L,int i,ElementType &e){ if(i<1){ printf("删除位置不合法！"); return false; } LNode *p=L; int j=0; while (p!=NULL&&j<i-1) { p=p->next; j++; } if(p==NULL){ printf("删除位置不合法！"); return false; } LNode *q=p->next; p->next=q->next; e=q->data; free(q); return true; }