文章目錄
單連結清單
#include<stdio.h>
#include<stdlib.h>
#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
} LNode,*LinkList;
LinkList List_HeadInsert(LinkList &L)
{
LNode *s;
int x;
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
scanf("%d",&x);
while(x!=9999)
{
s = (LinkList)malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
L->next = s;
scanf("%d",&x);
}
return L;
}
LinkList List_TailInsert(LinkList &L)
{
int x;
L = (LinkList)malloc(sizeof(LNode));
LNode *s,*r = L;
scanf("%d",&x);
while(x!=9999)
{
s=(LNode *)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s;
scanf("%d",&x);
}
r->next = NULL;
return L;
}
LNode *GetElem(LinkList L,int i)
{
int j = 1;
LNode *p = L->next;
if(i==0)
return L;
if(i<1)
return NULL;
while(p&&j<i)
{
p = p->next;
j++;
}
return p;
}
LNode *LocateElem(LinkList L,ElemType e)
{
LNode *p = L->next;
while(p!=NULL&&p->data!=e)
p=p->next;
return p;
}
void InsertNode_After(LinkList &L){
LNode *tmp = (LNode *)malloc(sizeof(LNode));
int value;
printf("%s","輸入要插入節點的值:");
scanf("%d",&value);
tmp->data = value;
printf("%s\n","舉例插傳入連結表的第二個元素的後面");
LinkList secondary = GetElem(L,2);
if(secondary==NULL)
printf("%s\n","連結清單的長度小于二,插入失敗");
else{
tmp->next = secondary->next;
secondary->next = tmp;
printf("%s\n","插入成功");
}
}
void InsertNode_Before(LinkList &L){
LNode *tmp = (LNode *)malloc(sizeof(LNode));
int value;
printf("%s","輸入要插入節點的值:");
scanf("%d",&value);
tmp->data = value;
printf("%s\n","舉例插傳入連結表的第二個元素的前面");
LinkList secondary = GetElem(L,2);
if(secondary==NULL)
printf("%s\n","連結清單的長度小于二,插入失敗");
else{
tmp->next = secondary->next;
secondary->next = tmp;
// 通過交換前後兩個節點的值,獲得在節點前面插入的效果,移魂幻影大法
int tmpData = tmp->data;
tmp->data = secondary->data;
secondary->data = tmpData;
printf("%s\n","插入成功");
}
}
void DeleteNode(LinkList &l,int index){
LinkList nodeOne = GetElem(l,index-1);
if(nodeOne->next==NULL){
printf("%s\n","連結清單的長度小于二,删除失敗");
}else{
LinkList deleteNode = nodeOne->next;
nodeOne->next = deleteNode->next;
free(deleteNode);
}
}
int GetLength(LinkList l){
int res = 0;
LinkList p = l->next;
while(p!=NULL){
res++;
p=p->next;
}
return res;
}
int main()
{
LinkList l;
l = List_TailInsert(l);// 尾插法建構連結清單
LinkList p = l->next;
// 周遊連結清單
printf("%s\n","原始連結清單:");
while(p!=NULL)
{
if(p->next!=NULL)
cout<<p->data<<endl;
else
cout<<p->data<<endl;
p = p->next;
}
// 根據元素的位置查找節點
// LinkList nodeOne = GetElem(l,2);
// if(nodeOne==NULL){
// printf("%s","沒有此節點\n");
// }else{
// cout<<nodeOne->data<<endl;
// }
// 根據元素的值查找節點
// LinkList nodeTwo = LocateElem(l,33);
// if(nodeTwo==NULL){
// printf("%s","沒有此節點\n");
// }
// else{
// cout<<nodeTwo->data<<endl;
// }
// 建構一個結點,并把它插入到指定節點的後面
// InsertNode_After(l);
// 建構一個結點,并把它插入到指定節點的前面
// InsertNode_Before(l);
// 假如我們删除第二個節點
DeleteNode(l,2);
int length = GetLength(l);
printf("目前連結清單的長度為:%d\n",length);
p = l->next;
// 周遊連結清單
printf("%s\n","一波操作後的連結清單:");
while(p!=NULL)
{
if(p->next!=NULL)
cout<<p->data<<endl;
else
cout<<p->data<<endl;
p = p->next;
}
return 0;
}
雙向連結清單
#include<stdlib.h>
#include<iostream>
#include<stdio.h>
using namespace std;
typedef int ElemType;
typedef struct DNode{
ElemType data;
struct DNode *prior,*next;
}DNode,*DLinkList;
DLinkList CreateDLinkList(DLinkList &l){
l = (DLinkList)malloc(sizeof(DNode));
DLinkList tmp = (DLinkList)malloc(sizeof(DNode));
tmp->data = 1000;
tmp->prior = l;
tmp->next = NULL;
l->next = tmp;
l->prior = NULL;
return l;
}
DLinkList GetElem(DLinkList l,int index){
DLinkList p = l->next;
int j = 1;
while(p!=NULL&&j<index){
p = p->next;
j++;
}
return p;
}
void InsertAfter(DLinkList p){
DLinkList tmp = (DLinkList)malloc(sizeof(DNode));
int value;
printf("輸入元素值:\n");
scanf("%d",&value);
tmp->data = value;
tmp->next = p->next;
p->next->prior = tmp;
tmp->prior = p;
p->next = tmp;
}
void DeleteAfter(DLinkList l){
DLinkList tmp = GetElem(l,1);
tmp->prior->next = tmp->next;
tmp->next->prior = tmp->prior;
free(tmp);
}
int main()
{
DLinkList l;
l = CreateDLinkList(l);
// 假設我們擷取的是第一個節點
DLinkList node = GetElem(l,1);
if(node!=NULL)
printf("%d\n",node->data);
// 在頭結點後面插入一個結點
InsertAfter(l);
// 删除頭結點後面的第一個元素
DeleteAfter(l);
// 周遊連結清單
DLinkList p = l->next;
while(p!=NULL){
printf("%d\n",p->data);
p=p->next;
}
return 0;
}
單循環連結清單
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
typedef int ElemType;
typedef struct CNode{
ElemType data;
struct CNode *next;
}CNode,*CLinkList;
CLinkList CreatCLinkList(CLinkList &l){
l = (CLinkList)malloc(sizeof(CNode));
l->next = l;
return l;
}
void InsertAfterHead(CLinkList &l){
CLinkList tmp = (CLinkList)malloc(sizeof(CNode));
int value;
scanf("%d",&value);
tmp->data = value;
tmp->next = l->next;
l->next = tmp;
}
void InsertAfterNode(CLinkList node){
CLinkList tmp = (CLinkList)malloc(sizeof(CNode));
int value;
scanf("%d",&value);
tmp->data = value;
tmp->next = node->next;
node->next = tmp;
}
CLinkList GetElem(CLinkList l,int index){
if(index==1)
return l->next;
else{
int j = 2;
CLinkList p = l->next->next;
while(p!=l->next&&j<index){
p = p->next;
j++;
}
if(p==l->next)
return NULL;
else
return p;
}
}
void DeleteTail(CLinkList &l){
CLinkList nodeTmp = GetElem(l,1);
CLinkList tmp = nodeTmp->next;
nodeTmp->next = tmp->next;
free(tmp);
}
int main()
{
CLinkList l;
l = CreatCLinkList(l);
// 頭結點後插入一個節點
InsertAfterHead(l);
CLinkList node = GetElem(l,1);
printf("%d\n",node->data);
InsertAfterNode(node);
// 删除尾節點
DeleteTail(l);
// 連結清單判空的條件
if(l->next==l)
printf("%s\n","連結清單為空");
else if(l->next->next==l){
printf("連結清單中隻有一個元素,其值為%d\n",l->next->data);
}
else{
CLinkList p = l->next;
while(p->next!=l){
printf("%d\n",p->data);
p=p->next;
}
cout<<p->data<<endl;
}
return 0;
}
![樹的基本概念(定義、基本術語、性質)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)