資料結構部分總結
Github下載下傳代碼：代碼連結
線性結構
線性表
順序表
優缺點
相關代碼
#include<stdio.h>
#include<stdbool.h>
#define Initlength 100
typedef struct{
int *list;
int length;
int size;
}linear_list;
void InitList(linear_list*L){
L->list=(int*)malloc(sizeof(int)*Initlength);
memset(L->list,0,sizeof(int)*L->length);
L->length=0;
L->size=Initlength;
}
void ListLength(linear_list*L){
printf("This list's length is %d\n",L->length);
}
void GetData(linear_list*L,int i){
printf("%d\n",L->list[i]);
}
void InsList(linear_list*L,int i,int value){
for(int j=i+1;j<=L->length;j++){
L->list[j]=L->list[j-1];
}
L->list[i]=value;
L->length++;
}
void DelList(linear_list*L,int i){
printf("Deleted value is %d\n",L->list[i]);
for(int j=i;j<L->length-1;j++){
L->list[j]=L->list[j+1];
}
L->length--;
}
void Locate(linear_list*L,int value){
for(int j=0;j<L->length;j++){
if(L->list[j]==value){
printf("The index is %d\n",j);
}else if(j==L->length-1){
printf("Can't find value %d\n",value);
}
}
}
void DestroyList(linear_list*L){
L->size=0;
L->length=0;
free(L->list);
}
void ClearList(linear_list*L){
memset(L->list,0,sizeof(int)*L->length);
}
bool EmptyList(linear_list*L){
if(L->length){
return false;
}else{
return true;
}
}
int main(){
linear_list *L=(linear_list *)malloc(sizeof(linear_list));
int choice,unfinished=1,x,v;
printf("Please input your command:\n");
printf("*** 0.Exit ***\n");
printf("*** 1.InitList ***\n");
printf("*** 2.ListLength ***\n");
printf("*** 3.GetData ***\n");
printf("*** 4.InsList ***\n");
printf("*** 5.DelList ***\n");
printf("*** 6.Locate ***\n");
printf("*** 7.DestroyList ***\n");
printf("*** 8.ClearList ***\n");
printf("*** 9.EmptyList ***\n");
while(unfinished){
scanf("%d",&choice);
switch(choice){
case 1:InitList(L);break;
case 2:ListLength(L);break;
case 3:
printf("Please input the index:");
scanf("%d",&x);
GetData(L,x);
break;
case 4:
printf("Please input the index:");
scanf("%d",&x);
printf("Please input the value:");
scanf("%d",&v);
InsList(L,x,v);
break;
case 5:
printf("Please input the index:");
scanf("%d",&x);
DelList(L,x);
break;
case 6:
printf("Please input the value:");
scanf("%d",&v);
Locate(L,v);
break;
case 7:
DestroyList(L);
break;
case 8:
ClearList(L);
break;
case 9:
if(EmptyList(L)){
printf("True.\n");
}
else{
printf("False.\n");
}
break;
default:unfinished=0;
}
printf("Finished.\n");
}
return 0;
}
連結清單
優缺點
- 插入删除操作友善
- 無法直接通路元素
- 查找耗時長
- 存儲密度小于1
相關代碼
#include <stdio.h>
#include <stdlib.h>
#define ElemType char
typedef struct{
ElemType data;
int length;
struct Node*next;
}Node,*LinkList;
void InitLink(LinkList *LP){
*LP=(LinkList)malloc(sizeof(Node));
(*LP)->length=0;
(*LP)->next=NULL;
}
void CreateFromHead(LinkList L){
LinkList t;
ElemType ch;
while(1){
printf("Please input element(end with '$'):");
getchar();
ch=getchar();
if(ch=='$')break;
t=(Node*)malloc(sizeof(Node));
t->data=ch;
t->next=L->next;
L->next=t;
L->length++;
}
}
void CreateFromTail(LinkList L){
LinkList p=L,t;
ElemType ch;
while(1){
printf("Please input element(end with '$'):");
getchar();
ch=getchar();
if(ch=='$')break;
t=(Node*)malloc(sizeof(Node));
t->data=ch;
p->next=t;
p=p->next;
L->length++;
}
p->next=NULL;
}
LinkList Locate(LinkList L,ElemType value){
LinkList p=L;
while(p){
if(p->data==value){
return p;
}
p=p->next;
}
printf("Can't find the value.\n");
return NULL;
}
ElemType Get(LinkList L,int i){
LinkList p=L;
for(int j=0;j<i;j++){
p=p->next;
}
return p->data;
}
void DelList(LinkList L,int i){
L->length--;
LinkList p=L,pre;
for(int j=0;j<i;j++){
pre=p;
p=p->next;
}
pre->next=p->next;
printf("The value is %c\n",p->data);
free(p);
}
void InsList(LinkList L,int i,ElemType value){
L->length++;
LinkList p=L,t;
for(int j=0;j<i-1;j++){
p=p->next;
}
t=(LinkList*)malloc(sizeof(Node));
t->data=value;
t->next=p->next;
p->next=t;
}
LinkList MergeList(LinkList L1,LinkList L2){
LinkList L;
InitLink(&L);
L->next=L1->next;
while(L1->next!=NULL){
L1=L1->next;
}
L1->next=L2->next;
L->length=L1->length+L2->length;
return L;
}
int main()
{
LinkList L,L1,L2;
int choice,unfinished=1,x;
ElemType v;
printf("Please input your command:\n");
printf("*** 0.Exit \t\t\t***\n");
printf("*** 1.InitLink\t\t\t***\n");
printf("*** 2.CreateFromHead\t\t\t***\n");
printf("*** 3.CreateFromTail\t\t\t***\n");
printf("*** 4.Locate \t\t\t***\n");
printf("*** 5.Get \t\t\t***\n");
printf("*** 6.DelList \t\t\t***\n");
printf("*** 7.InsList\t\t\t***\n");
printf("*** 8.MergeList\t\t\t***\n");
while(unfinished){
scanf("%d",&choice);
switch(choice){
case 1:InitLink(&L);break;
case 2:CreateFromHead(L);break;
case 3:CreateFromTail(L);break;
case 4:
printf("Please input the value:");
getchar();
scanf("%c",&v);
if(Locate(L,v)){
printf("the value is in <%p>\n",Locate(L,v));
}
break;
case 5:
printf("Please input the index:");
scanf("%d",&x);
if(x>L->length||x<=0)printf("Can't find.\n");
else printf("The value is '%c'\n",Get(L,x));
break;
case 6:
printf("Please input the index:");
scanf("%d",&x);
if(x>L->length)printf("Out of range.\n");
else DelList(L,x);
break;
case 7:
printf("Please input the index:");
scanf("%d",&x);
printf("Please input the value:");
getchar();
scanf("%c",&v);
InsList(L,x,v);
break;
case 8:
InitLink(&L1);
InitLink(&L2);
printf("Initialize the L1(tail):\n");
CreateFromTail(L1);
printf("Initialize the L2(tail):\n");
CreateFromTail(L2);
L=MergeList(L1,L2);
break;
default:unfinished=0;
}
printf("Finished.\n");
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#define ElemType char
typedef struct{
ElemType data;
struct Node *prior,*next;
}Node,*LinkList;
void InitLink(LinkList *LP){
*LP=(LinkList)malloc(sizeof(Node));
(*LP)->next=NULL;
(*LP)->prior=NULL;
}
void CreateLink(LinkList L){
LinkList p=L,t;
ElemType value;
while(1){
printf("Please input element(end with '$'):");
getchar();
value=getchar();
if(value=='$')break;
t=(Node*)malloc(sizeof(Node));
t->data=value;
p->next=t;
t->prior=p;
p=p->next;
}
p->next=NULL;
}
void InsLink(LinkList L,int i,ElemType value){
//���������� ֻ���ñ�ı�����ʾp��ǰ��
LinkList p=L,t,s;
for(int j=0;j<i&&p;j++)p=p->next;
if(!p){
printf("The index is out of range.\n");
return;
}
s=p->prior;
t=(LinkList)malloc(sizeof(Node));
t->data=value;
t->prior=s;
s->next=t;
t->next=p;
p->prior=t;
}
void DelLink(LinkList L,int i){
//���������� ֻ���ñ�ı�����ʾp��ǰ��
LinkList p=L,s,t;
for(int j=0;j<i&&p;j++)p=p->next;
if(p)printf("The value is '%c'\n",p->data);
else{
printf("The index is out of range.\n");
return;
}
s=p->prior;
t=p->next;
s->next=p->next;
s->prior=p->prior;
free(p);
}
void Locate(LinkList L,int i){
LinkList p=L;
for(int j=0;j<i&&p;j++)p=p->next;
if(p)printf("The value is '%c'\n",p->data);
else{
printf("The index is out of range.\n");
return;
}
}
int main()
{
LinkList L,L1,L2;
int choice,unfinished=1,x;
ElemType v;
printf("Please input your command:\n");
printf("*** 0.Exit \t\t\t***\n");
printf("*** 1.InitLink\t\t\t***\n");
printf("*** 2.CreateLink\t\t\t***\n");
printf("*** 3.InsLink\t\t\t***\n");
printf("*** 4.DelLink \t\t\t***\n");
printf("*** 5.Locate \t\t\t***\n");
while(unfinished){
scanf("%d",&choice);
switch(choice){
case 1:InitLink(&L);break;
case 2:CreateLink(L);break;
case 3:
printf("Please input the index:");
scanf("%d",&x);
printf("Please input the value:");
getchar();
scanf("%c",&v);
InsLink(L,x,v);
break;
case 4:
printf("Please input the index:");
scanf("%d",&x);
DelLink(L,x);
break;
case 5:
printf("Please input the index:");
scanf("%d",&x);
Locate(L,x);
break;
default:unfinished=0;
}
printf("Finished.\n");
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#define ElemType char
typedef struct{
ElemType data;
struct Node*next;
}Node,*LinkList;
void InitLink(LinkList *LP){
*LP=(LinkList)malloc(sizeof(Node));
(*LP)->length=0;
(*LP)->next=*LP;
}
void CreateLink(LinkList L){
LinkList p=L,t;
ElemType value;
while(1){
printf("Please input element(end with '$'):");
getchar();
value=getchar();
if(value=='$')break;
t=(Node*)malloc(sizeof(Node));
t->data=value;
p->next=t;
p=p->next;
}
p->next=L;
}
LinkList MergeLink(LinkList L1,LinkList L2){
LinkList p1=L1,p2=L2;
while(p1->next!=L1)p1=p1->next;
while(p2->next!=L2)p2=p2->next;
p1->next=L2->next;
p2->next=L1;
free(L2);
return L1;
}
void Locate(LinkList L,int i){
LinkList p=L->next;
for(int j=0;j<i-1&&p!=L;j++){
p=p->next;
}
if(p==L)printf("The index is out of range.\n");
else printf("The value is '%c'\n",p->data);
}
int main()
{
LinkList L,L1,L2;
int choice,unfinished=1,x;
ElemType v;
printf("Please input your command:\n");
printf("*** 0.Exit \t\t\t***\n");
printf("*** 1.InitLink\t\t\t***\n");
printf("*** 2.CreateLink\t\t\t***\n");
printf("*** 3.MergeLink\t\t\t***\n");
printf("*** 4.Locate \t\t\t***\n");
while(unfinished){
scanf("%d",&choice);
switch(choice){
case 1:InitLink(&L);break;
case 2:CreateLink(L);break;
case 3:
InitLink(&L1);
InitLink(&L2);
printf("Initialize the L1:\n");
CreateLink(L1);
printf("Initialize the L2:\n");
CreateLink(L2);
L=MergeLink(L1,L2);
break;
case 4:
printf("Please input the index:");
scanf("%d",&x);
Locate(L,x);
break;
default:unfinished=0;
}
printf("Finished.\n");
}
return 0;
}
棧
相關代碼
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ElemType char
#define stack_size 100
typedef struct{
ElemType elem[stack_size];
int top;
}mystack;
bool IsEmpty(mystack*S){
if(S->top==-1){
printf("Stack is empty.\n");
return true;
}
else return false;
}
bool IsFull(mystack*S){
if(S->top==stack_size-1){
printf("Stack is full.\n");
return true;
}
else return false;
}
void InitStack(mystack**SP){
(*SP)=(mystack*)malloc(sizeof(mystack));
(*SP)->top=-1;
}
void Push(mystack*S,ElemType value){
if(IsFull(S))return;
S->elem[++S->top]=value;
}
bool Pop(mystack*S,ElemType*valuepoint){
if(IsEmpty(S))return false;
*valuepoint=S->elem[S->top--];
return true;
}
bool GetTop(mystack*S,ElemType*valuepoint){
if(IsEmpty(S))return false;
*valuepoint=S->elem[S->top];
return true;
}
int main()
{
mystack*S;
int choice,unfinished=1,x;
ElemType v;
printf("Please input your command:\n");
printf("*** 0.Exit \t\t\t***\n");
printf("*** 1.InitStack\t\t\t***\n");
printf("*** 2.Push \t\t\t***\n");
printf("*** 3.Pop \t\t\t***\n");
printf("*** 4.GetTop \t\t\t***\n");
while(unfinished){
scanf("%d",&choice);
switch(choice){
case 1:InitStack(&S);break;
case 2:
printf("Please input the value:");
getchar();
scanf("%c",&v);
Push(S,v);
break;
case 3:
if(Pop(S,&v))printf("The value is '%c'\n",v);
break;
case 4:
if(GetTop(S,&v))printf("The value is '%c'\n",v);
break;
default:unfinished=0;
}
printf("Finished.\n");
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ElemType char
#define stack_size 100
typedef struct{
ElemType elem[stack_size];
int top[2];
}mystack;
bool IsEmpty(mystack*S,int side){
switch(side){
case 0:
if(S->top[0]==-1){
printf("Left stack is empty.\n");
return true;
}
else return false;
break;
case 1:
if(S->top[1]==stack_size){
printf("Right stack is empty.\n");
return true;
}
else return false;
break;
}
}
bool IsFull(mystack*S){
if(S->top[0]==S->top[1]-1){
printf("Stack is full.\n");
return true;
}
else return false;
}
void InitStack(mystack**SP){
(*SP)=(mystack*)malloc(sizeof(mystack));
(*SP)->top[0]=-1;
(*SP)->top[1]=stack_size;
}
void Push(mystack*S,ElemType value,int side){
if(IsFull(S))return;
switch(side){
case 0:
S->elem[++S->top[0]]=value;
break;
case 1:
S->elem[--S->top[1]]=value;
break;
}
}
bool Pop(mystack*S,ElemType*valuepoint,int side){
if(IsEmpty(S,side))return false;
switch(side){
case 0:
*valuepoint=S->elem[S->top[0]--];
break;
case 1:
*valuepoint=S->elem[S->top[1]++];
break;
}
return true;
}
bool GetTop(mystack*S,ElemType*valuepoint,int side){
if(IsEmpty(S,side))return false;
switch(side){
case 0:
*valuepoint=S->elem[S->top[0]];
break;
case 1:
*valuepoint=S->elem[S->top[1]];
break;
}
return true;
}
int main()
{
mystack*S;
int choice,unfinished=1,x;
ElemType v;
printf("Please input your command:\n");
printf("*** 0.Exit \t\t\t***\n");
printf("*** 1.InitStack\t\t\t***\n");
printf("*** 2.Push \t\t\t***\n");
printf("*** 3.Pop \t\t\t***\n");
printf("*** 4.GetTop \t\t\t***\n");
while(unfinished){
scanf("%d",&choice);
switch(choice){
case 1:InitStack(&S);break;
case 2:
printf("Please input the side(left-0/right-1):");
scanf("%d",&x);
printf("Please input the value:");
getchar();
scanf("%c",&v);
Push(S,v,x);
break;
case 3:
printf("Please input the side(left-0/right-1):");
scanf("%d",&x);
if(Pop(S,&v,x))printf("The value is '%c'\n",v);
break;
case 4:
printf("Please input the side(left-0/right-1):");
scanf("%d",&x);
if(GetTop(S,&v,x))printf("The value is '%c'\n",v);
break;
default:unfinished=0;
}
printf("Finished.\n");
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ElemType char
typedef struct{
ElemType data;
struct Node*next;
}Node,*Mystack;
void InitStack(Mystack *SP){
*SP=(Mystack)malloc(sizeof(Node));
(*SP)->next=NULL;
}
void Push(Mystack S,ElemType value){
Mystack t;
t=(Node*)malloc(sizeof(Node));
t->data=value;
t->next=S->next;
S->next=t;
}
bool Pop(Mystack S,ElemType*valuepoint){
Mystack t=S->next;
if(t){
*valuepoint=t->data;
S->next=t->next;
free(t);
return true;
}
else{
printf("Stack is empty.\n");
return false;
}
}
int main()
{
Mystack S;
int choice,unfinished=1,x;
ElemType v;
printf("Please input your command:\n");
printf("*** 0.Exit \t\t\t***\n");
printf("*** 1.InitStack\t\t\t***\n");
printf("*** 2.Push \t\t\t***\n");
printf("*** 3.Pop \t\t\t***\n");
while(unfinished){
scanf("%d",&choice);
switch(choice){
case 1:InitStack(&S);break;
case 2:
printf("Please input the value:");
getchar();
scanf("%c",&v);
Push(S,v);
break;
case 3:
if(Pop(S,&v))printf("The value is '%c'\n",v);
break;
default:unfinished=0;
}
printf("Finished.\n");
}
return 0;
}
隊列
相關代碼
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ElemType char
#define queue_size 100
typedef struct{
ElemType elem[queue_size];
int top,rear;
}myqueue;
bool IsEmpty(myqueue*Q){
if(Q->top==Q->rear){
printf("Queue is empty.\n");
return true;
}
else return false;
}
bool IsFull(myqueue*Q){
if(Q->rear==queue_size-1){
printf("Queue is full.\n");
return true;
}
else return false;
}
void InitQueue(myqueue**QP){
(*QP)=(myqueue*)malloc(sizeof(myqueue));
(*QP)->top=-1;
(*QP)->rear=-1;
}
void Push(myqueue*Q,ElemType value){
if(IsFull(Q))return;
Q->elem[++Q->rear]=value;
}
bool Pop(myqueue*Q,ElemType*valuepoint){
if(IsEmpty(Q))return false;
*valuepoint=Q->elem[++Q->top];
return true;
}
bool GetTop(myqueue*Q,ElemType*valuepoint){
if(IsEmpty(Q))return false;
*valuepoint=Q->elem[Q->top+1];
return true;
}
void ClearQueue(myqueue*Q){
Q->top=Q->rear=-1;
}
int main()
{
myqueue*Q;
int choice,unfinished=1,x;
ElemType v;
printf("Please input your command:\n");
printf("*** 0.Exit \t\t\t***\n");
printf("*** 1.InitQueue\t\t\t***\n");
printf("*** 2.Push \t\t\t***\n");
printf("*** 3.Pop \t\t\t***\n");
printf("*** 4.GetTop \t\t\t***\n");
printf("*** 5.ClearQueue\t\t\t***\n");
while(unfinished){
scanf("%d",&choice);
switch(choice){
case 1:InitQueue(&Q);break;
case 2:
printf("Please input the value:");
getchar();
scanf("%c",&v);
Push(Q,v);
break;
case 3:
if(Pop(Q,&v))printf("The value is '%c'\n",v);
break;
case 4:
if(GetTop(Q,&v))printf("The value is '%c'\n",v);
break;
case 5:ClearQueue(Q);break;
default:unfinished=0;
}
printf("Finished.\n");
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ElemType char
typedef struct{
ElemType data;
struct Node*next;
}Node,*LinkQueue;
typedef struct{
LinkQueue top;
LinkQueue rear;
}LinkPointer;
void InitQueue(LinkPointer *Q){
Q->top=(Node*)malloc(sizeof(Node));
Q->rear=Q->top;
LinkQueue t=Q->rear;
t->next=NULL;
}
void Push(LinkPointer*Q,ElemType value){
LinkQueue t,s;
t=(Node*)malloc(sizeof(Node));
t->next=NULL;
t->data=value;
s=Q->rear;
s->next=t;
Q->rear=t;
}
bool Pop(LinkPointer*Q,ElemType*valuepoint){
LinkQueue t=Q->top,s;
t=t->next;
if(Q->rear==Q->top){
printf("Queue is empty.\n");
return false;
}
*valuepoint=t->data;
s=Q->top;
s->next=t->next;
if(t==Q->rear){
Q->rear=Q->top;
}
free(t);
return true;
}
bool GetTop(LinkPointer*Q,ElemType*valuepoint){
LinkQueue t=Q->top;
t=t->next;
if(Q->rear==Q->top){
printf("Queue is empty.\n");
return false;
}
*valuepoint=t->data;
return true;
}
void ClearQueue(LinkPointer*Q){
ElemType value;
while(Q->rear!=Q->top)Pop(Q,&value);
}
int main()
{
LinkPointer*Q=(LinkPointer*)malloc(sizeof(LinkPointer));
int choice,unfinished=1,x;
ElemType v;
printf("Please input your command:\n");
printf("*** 0.Exit \t\t\t***\n");
printf("*** 1.InitQueue\t\t\t***\n");
printf("*** 2.Push \t\t\t***\n");
printf("*** 3.Pop \t\t\t***\n");
printf("*** 4.GetTop \t\t\t***\n");
printf("*** 5.ClearQueue\t\t\t***\n");
while(unfinished){
scanf("%d",&choice);
switch(choice){
case 1:InitQueue(Q);break;
case 2:
printf("Please input the value:");
getchar();
scanf("%c",&v);
Push(Q,v);
break;
case 3:
if(Pop(Q,&v))printf("The value is '%c'\n",v);
break;
case 4:
if(GetTop(Q,&v))printf("The value is '%c'\n",v);
break;
case 5:ClearQueue(Q);break;
default:unfinished=0;
}
printf("Finished.\n");
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ElemType char
#define queue_size 5
typedef struct{
ElemType elem[queue_size];
int top,rear,cnt;
}myqueue;
bool IsEmpty(myqueue*Q){
if(Q->cnt==0){
printf("Queue is empty.\n");
return true;
}
else return false;
}
bool IsFull(myqueue*Q){
if(Q->cnt==queue_size){
printf("Queue is full.\n");
return true;
}
else return false;
}
void InitQueue(myqueue**QP){
(*QP)=(myqueue*)malloc(sizeof(myqueue));
(*QP)->top=0;
(*QP)->rear=0;
(*QP)->cnt=0;
}
void Push(myqueue*Q,ElemType value){
if(IsFull(Q))return;
Q->elem[++Q->rear%queue_size]=value;
Q->cnt++;
}
bool Pop(myqueue*Q,ElemType*valuepoint){
if(IsEmpty(Q))return false;
*valuepoint=Q->elem[++Q->top%queue_size];
Q->cnt--;
return true;
}
bool GetTop(myqueue*Q,ElemType*valuepoint){
if(IsEmpty(Q))return false;
*valuepoint=Q->elem[Q->top+1%queue_size];
return true;
}
void ClearQueue(myqueue*Q){
Q->top=Q->rear=-1;
}
int main()
{
myqueue*Q;
int choice,unfinished=1,x;
ElemType v;
printf("Please input your command:\n");
printf("*** 0.Exit \t\t\t***\n");
printf("*** 1.InitQueue\t\t\t***\n");
printf("*** 2.Push \t\t\t***\n");
printf("*** 3.Pop \t\t\t***\n");
printf("*** 4.GetTop \t\t\t***\n");
printf("*** 5.ClearQueue\t\t\t***\n");
while(unfinished){
scanf("%d",&choice);
switch(choice){
case 1:InitQueue(&Q);break;
case 2:
printf("Please input the value:");
getchar();
scanf("%c",&v);
Push(Q,v);
break;
case 3:
if(Pop(Q,&v))printf("The value is '%c'\n",v);
break;
case 4:
if(GetTop(Q,&v))printf("The value is '%c'\n",v);
break;
case 5:ClearQueue(Q);break;
default:unfinished=0;
}
printf("Finished.\n");
}
return 0;
}
數組
三元組
相關代碼
#include <stdio.h>
#include <stdlib.h>
#define ElemType char
typedef struct{
ElemType data;
struct Node*next;
}Node,*LinkList;
void InitLink(LinkList *LP){
*LP=(LinkList)malloc(sizeof(Node));
(*LP)->length=0;
(*LP)->next=*LP;
}
void CreateLink(LinkList L){
LinkList p=L,t;
ElemType value;
while(1){
printf("Please input element(end with '$'):");
getchar();
value=getchar();
if(value=='$')break;
t=(Node*)malloc(sizeof(Node));
t->data=value;
p->next=t;
p=p->next;
}
p->next=L;
}
LinkList MergeLink(LinkList L1,LinkList L2){
LinkList p1=L1,p2=L2;
while(p1->next!=L1)p1=p1->next;
while(p2->next!=L2)p2=p2->next;
p1->next=L2->next;
p2->next=L1;
free(L2);
return L1;
}
void Locate(LinkList L,int i){
LinkList p=L->next;
for(int j=0;j<i-1&&p!=L;j++){
p=p->next;
}
if(p==L)printf("The index is out of range.\n");
else printf("The value is '%c'\n",p->data);
}
int main()
{
LinkList L,L1,L2;
int choice,unfinished=1,x;
ElemType v;
printf("Please input your command:\n");
printf("*** 0.Exit \t\t\t***\n");
printf("*** 1.InitLink\t\t\t***\n");
printf("*** 2.CreateLink\t\t\t***\n");
printf("*** 3.MergeLink\t\t\t***\n");
printf("*** 4.Locate \t\t\t***\n");
while(unfinished){
scanf("%d",&choice);
switch(choice){
case 1:InitLink(&L);break;
case 2:CreateLink(L);break;
case 3:
InitLink(&L1);
InitLink(&L2);
printf("Initialize the L1:\n");
CreateLink(L1);
printf("Initialize the L2:\n");
CreateLink(L2);
L=MergeLink(L1,L2);
break;
case 4:
printf("Please input the index:");
scanf("%d",&x);
Locate(L,x);
break;
default:unfinished=0;
}
printf("Finished.\n");
}
return 0;
}
字元串
順序串
相關代碼
#include<stdio.h>
#include<stdbool.h>
#define ElemType char
#define Initlength 100
typedef struct{
ElemType *list;
int length;
int size;
}mystring;
void InitString(mystring*S){
S->list=(ElemType*)malloc(sizeof(ElemType)*Initlength);
S->length=0;
S->size=Initlength;
}
void StringLength(mystring*S){
printf("This list's length is %d\n",S->length);
}
void GetData(mystring*S,int i){
printf("%c\n",S->list[i]);
}
void InsString(mystring*S,int i,ElemType value){
for(int j=i+1;j<=S->length;j++){
S->list[j]=S->list[j-1];
}
S->list[i]=value;
S->length++;
}
void DelString(mystring*S,int i){
printf("Deleted value is %d\n",S->list[i]);
for(int j=i;j<S->length-1;j++){
S->list[j]=S->list[j+1];
}
S->length--;
}
void Locate(mystring*S,ElemType value){
for(int j=0;j<S->length;j++){
if(S->list[j]==value){
printf("The index is %d\n",j);
}else if(j==S->length-1){
printf("Can't find value %c\n",value);
}
}
}
bool BruteForce(mystring*S1,mystring*S2){
int i1,i2;
for(i1=0;i1<S1->length;i1++){
for(i2=0;i2<S2->length;i2++){
if(S1->list[i1]!=S2->list[i2])break;
}
if(i2==S2->length) return true;
}
return false;
}
bool KMP(mystring*S1,mystring*S2){
int i=0,j=0,n=S1->length,m=S2->length,k=-1,next[S2->length];
next[0]=-1;
while(j<n){
if(k==-1||S2->list[j]==S2->list[k]){
next[++j]=++k;
}
else k=next[k];
}
while(i<=n-m){
while(j==-1||(S2->list[j]==S1->list[i]&&j<m)){
i++;j++;
}
if(j==m)return true;
else j=next[j];
}
return false;
}
bool CompareString(mystring*S1,mystring*S2){
int i1,i2;
for(i1=0,i2=0;i1<S1->length&&i2<S2->length;i1++,i2++){
if(S1->list[i1]!=S2->list[i2])break;
}
if(i1==S1->length&&i2==S2->length)return true;
else return false;
}
int main(){
mystring *S=(mystring *)malloc(sizeof(mystring));
mystring *Sp=(mystring *)malloc(sizeof(mystring));
int choice,unfinished=1,x,stop=0;
ElemType v;
printf("Please input your command:\n");
printf("*** 0.Exit ***\n");
printf("*** 1.InitString ***\n");
printf("*** 2.StringLength ***\n");
printf("*** 3.GetData ***\n");
printf("*** 4.InsString ***\n");
printf("*** 5.DelString ***\n");
printf("*** 6.Locate ***\n");
printf("*** 7.BruteForce ***\n");
printf("*** 8.KMP ***\n");
printf("*** 9.CompareString ***\n");
while(unfinished){
scanf("%d",&choice);
switch(choice){
case 1:InitString(S);break;
case 2:StringLength(S);break;
case 3:
printf("Please input the index:");
scanf("%d",&x);
GetData(S,x);
break;
case 4:
printf("Please input the index:");
scanf("%d",&x);
printf("Please input the value:");
getchar();
v=getchar();
InsString(S,x,v);
break;
case 5:
printf("Please input the index:");
scanf("%d",&x);
DelString(S,x);
break;
case 6:
printf("Please input the value:");
getchar();
v=getchar();
Locate(S,v);
break;
case 7:
printf("Initialize the S':\n");
InitString(Sp);
for(int i=0;!stop;i++){
printf("Please input the value:");
getchar();
v=getchar();
InsString(Sp,i,v);
printf("Do you want to stop?[1/0]");
scanf("%d",&stop);
}
if(BruteForce(S,Sp))printf("S' is S's substring.\n");
else printf("S' is not S's substring.\n");
break;
case 8:
printf("Initialize the S':\n");
InitString(Sp);
for(int i=0;!stop;i++){
printf("Please input the value:");
getchar();
v=getchar();
InsString(Sp,i,v);
printf("Do you want to stop?[1/0]");
scanf("%d",&stop);
}
if(KMP(S,Sp))printf("S' is S's substring.\n");
else printf("S' is not S's substring.\n");
break;
case 9:
printf("Initialize the S':\n");
InitString(Sp);
for(int i=0;!stop;i++){
printf("Please input the value:");
getchar();
v=getchar();
InsString(Sp,i,v);
printf("Do you want to stop?[1/0]");
scanf("%d",&stop);
}
if(CompareString(S,Sp))printf("Compared.\n");
else printf("Not compared.\n");
break;
default:unfinished=0;
}
stop=0;
printf("Finished.\n");
}
return 0;
}
鍊串
相關代碼
#include <stdio.h>
#include <stdlib.h>
#define BlOCK_SIZE 4
#define ElemType char
typedef struct Block{
ElemType b[BlOCK_SIZE];
struct Block*next;
}Block;
typedef struct{
Block*head;
Block*tail;
int length;
}BlockString;
void InitBlock(BlockString *B){
B->length=0;
B->head=(Block*)malloc(sizeof(Block));
B->tail=B->head;
Block* t=B->tail;
t->next=NULL;
}
void BlockLength(BlockString*B){
printf("Block's length is %d\n",B->length);
}
void GetData(BlockString*B,int i){
if(B->length<i){
printf("The index is out of range.\n");
return;
}
Block*p=B->head;
for(;i>0;i--)p=p->next;
printf("The value is '%s'\n",p->b);
}
void InsBlock(BlockString*B,int i,ElemType*value){
int flag=0;
Block *t=(Block*)malloc(sizeof(Block)),*p=B->head;
B->length++;
for(int j=0;j<BlOCK_SIZE;j++){
if(value[j]=='\0'){
flag=1;
}
if(flag){
t->b[j]='#';
}else{
t->b[j]=value[j];
}
}
for(;i>1;i--)p=p->next;
t->next=p->next;
p->next=t;
}
void DelBlock(BlockString*B,int i){
if(B->length<i){
printf("The index is out of range.\n");
return;
}
Block*p=B->head,*t;
for(;i>1;i--)p=p->next;
t=p->next;
printf("The value is '%s'\n",t->b);
p->next=t->next;
free(p);
}
int main()
{
BlockString *B=(BlockString *)malloc(sizeof(BlockString));
int choice,unfinished=1,x;
ElemType*v=(ElemType*)malloc(sizeof(char)*BlOCK_SIZE);
printf("Please input your command:\n");
printf("*** 0.Exit ***\n");
printf("*** 1.InitList ***\n");
printf("*** 2.BlockLength ***\n");
printf("*** 3.GetData ***\n");
printf("*** 4.InsList ***\n");
printf("*** 5.DelList ***\n");
while(unfinished){
scanf("%d",&choice);
switch(choice){
case 1:InitBlock(B);break;
case 2:BlockLength(B);break;
case 3:
printf("Please input the index:");
scanf("%d",&x);
GetData(B,x);
break;
case 4:
printf("Please input the index:");
scanf("%d",&x);
printf("Please input the value:");
getchar();
gets(v);
InsBlock(B,x,v);
break;
case 5:
printf("Please input the index:");
scanf("%d",&x);
DelBlock(B,x);
break;
default:unfinished=0;
}
printf("Finished.\n");
}
return 0;
}
非線性結構
樹
#include<bits/stdc++.h>
#define N 30
#define Stack_Size 50
typedef struct Node
{
char v;
struct Node* lchild, * rchild;
}Tree, * TreePointer;
typedef struct {
TreePointer elem[Stack_Size];
int top;
}Stack;
typedef struct
{
TreePointer elem[Stack_Size];
int top, tail;
}Queue;
TreePointer tree, ft;
int n, i;
const char Tree_s[N] = { 'A','B','D','G','#','#','#','E','#','H','I','#','#','#','C','#','F','#','#' };
int build_tree(TreePointer x) {
TreePointer p = x;
char t;
n++;
t = Tree_s[i++];
if (t == '#') {
p->v = '#';
p = NULL;
}
else {
p->v = t;
p->lchild = (TreePointer)malloc(sizeof(Tree));
p->rchild = (TreePointer)malloc(sizeof(Tree));
build_tree(p->lchild);
build_tree(p->rchild);
}
return 0;
}
void proorder_traversal(TreePointer x) {
if (x->v != '#') {
printf("%c", x->v);
proorder_traversal(x->lchild);
proorder_traversal(x->rchild);
}
return;
}
void inorder_traversal(TreePointer x) {
if (x->v != '#') {
inorder_traversal(x->lchild);
printf("%c", x->v);
inorder_traversal(x->rchild);
}
return;
}
void posorder_traversal(TreePointer x) {
if (x->v != '#') {
posorder_traversal(x->lchild);
posorder_traversal(x->rchild);
printf("%c", x->v);
}
return;
}
void rninorder_traversal(TreePointer x) {
TreePointer p = x;
Stack tp;
tp.top = -1;
while (p->v != '#' || tp.top != -1) {
while (p->v != '#') {
tp.elem[++tp.top] = p;
p = p->lchild;
}
if (tp.top != -1) {
p = tp.elem[tp.top--];
printf("%c", p->v);
p = p->rchild;
}
}
return;
}
void rnposorder_traversal(Tree x) {
TreePointer p = &x, q = NULL;
Stack tp;
tp.top = -1;
while (p->v != '#' || tp.top != -1) {
while (p->v != '#') {
tp.elem[++tp.top] = p;
p = p->lchild;
}
if (tp.top != -1) {
p = tp.elem[tp.top];
if (p->rchild->v == '#' || p->rchild == q) {
printf("%c", p->v);
q = p;
tp.top--;
p->v = '#';
}
else p = p->rchild;
}
}
return;
}
void level_traversal(TreePointer x) {
TreePointer p = x;
Queue tq;
tq.top = -1;
tq.tail = 0;
tq.elem[tq.tail] = p;
while (tq.tail != tq.top) {
p = tq.elem[++tq.top];
printf("%c", p->v);
if (p->lchild->v != '#')tq.elem[++tq.tail] = p->lchild;
if (p->rchild->v != '#')tq.elem[++tq.tail] = p->rchild;
}
}
int path(TreePointer root, TreePointer node, Stack* s)
{
TreePointer p = root, q = NULL;
Stack* t = (Stack*)malloc(sizeof(Stack));
t->top = -1;
while (p->v != '#' || t->top != -1) {
while (p->v != '#' && p != node) {
t->elem[++t->top] = p;
s->elem[++s->top] = p;
p = p->lchild;
}
if (p == node) {
s->elem[++s->top] = p;
return 1;
}
if (t->top != -1) {
p = t->elem[t->top];
if (p->rchild->v == '#' || p->rchild == q) {
q = p;
t->top--;
s->top--;
p->v = '#';
}
else p = p->rchild;
}
}
return 0;
}
int main() {
tree = (TreePointer)malloc(sizeof(Tree));
build_tree(tree);
rninorder_traversal(tree);
printf("\n");
Stack* s = (Stack*)malloc(sizeof(Stack));
s->top = -1;
TreePointer node = tree->lchild->rchild->rchild->lchild;
path(tree, node, s);
while (s->top != -1) {
printf("%c", s->elem[s->top--]->v);
}
return 0;
}
![樹的基本概念(定義、基本術語、性質)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)