単鎖表操作大全(図解逆序)
9783 ワード
linuxでよくやったり、kernelの下で仕事をしたりすると、チェーンテーブルの操作にぶつかるに違いありません.もしあなたが本当に単鎖表を理解していないなら、基礎を作ったほうがいいでしょう.次のプログラムはチェーンテーブルの一般的な面を総合して、自分で各関数を書いて、debugして実行して、正しく実行するまで実行してください.それから参考プログラムと照らし合わせて、プログラムの違いを比較して、时には、あなたはテストが全面的ではないかもしれませんが、このような間違いがあって、多く考えて、このようにして、あなたはやっと記憶しています.
もし、前のいくつかの操作をよく知っていれば、単鎖表逆序はあなたの能力を試すことができます.(実は難しくありません)、肝心なのは構想がはっきりしていることです.まず、単鎖表逆序の原理を見てみましょう.もしあなたが理解を間違えたら、プログラムも書けないかもしれません.原理は図のように示しています.
ここではプログラム中の逆シーケンス関数を解析し,特に,ここの単一チェーンテーブルはheaderを含む単一チェーンテーブルであることを提案した.図を描くのに便利なために、ここではチェーンテーブルに3つしかないと仮定します.1,2,3.より多くの場合は同じです.各文の意味は図で詳細に説明されています.
付1:チェーンヘッダのない単一チェーンテーブル逆シーケンスプログラム
付2:ノーマルシングルチェーンテーブルからノードタイトルを削除する:
ヘッダポインタのない単一チェーンテーブルがあると仮定します.1つのポインタは、この単一チェーンテーブルの中間にあるノード(最初のノードでも最後のノードでもない)を指します.ノードを単一チェーンテーブルから削除してください.
回答:
典型的な「たぬき交換太子」では,このノードを削除するには通常,そのノードの前面ノードのポインタを知るべきであるが,単鎖表にはヘッダノードがないため,そのノードの前面のノードに遡ることができないため,ここでは「移花接木」の手法を採った.このノードをB,次のノードをCとする.では,まずBノードの内容をCノードの内容に置き換え,その後,Cノードを削除することで我々の目的を達成する.コードは次のとおりです.
コード#コード#
類似の問題:
1、無頭単鎖表からノードを削除する問題:頭ポインタのない単鎖表があると仮定し、1つのポインタpが単鎖表の1つのノード(最初でも最後でもない)を指している場合、そのノードを削除してください.
2、ヘッドレス単一チェーンテーブルにノードを追加する問題:ヘッドポインタのない単一チェーンテーブルがあると仮定し、1つのポインタpが単一チェーンテーブルの1つのノード(最初でも最後でもない)を指すと仮定し、そのノードの前に新しいノードqを挿入してください.
チェーンテーブルはヘッダレス一方向チェーンテーブルであるため、現在のノードを削除しても、前のノードに新しいノードを挿入しても、pの前のノードを取得する必要があります.ここでは考えを変えて,現在のノードの後続ノードを操作し,前後のノードのデータを適切に交換しても相応の効果が得られる.
問題1解法:p後継ノードp->nextのデータをpにコピーし、p->nextを削除すると、同じ効果が得られます.コードは以下の通りです.
問題2解法:pノードの後にqを追加し,pとqのデータを交換すればよい.
拡張の問題:
1つの単一チェーンテーブルを、1回だけ巡回する場合に、単一チェーンテーブルの要素を順番に反転します.
回答:
私の考えはこのようにして、3つのポインタで遍歴して、遍歴の途中で、逆置を行います.
#include
#include
typedef struct node
{
int nDate;
struct node *pstnext;
}Node;
//
void output(Node *head)
{
Node *p = head->pstnext;
while(NULL != p)
{
printf("%d ", p->nDate);
p = p->pstnext;
}
printf("\r
");
}
//
Node* creat()
{
Node *head = NULL, *p = NULL, *s = NULL;
int Date = 0, cycle = 1;
head = (Node*)malloc(sizeof(Node));
if(NULL == head)
{
printf(" \r
");
return NULL;
}
head->pstnext = NULL;
p = head;
while(cycle)
{
printf(" 0 \r
");
scanf("%d", &Date);
if(0 != Date)
{
s = (Node*)malloc(sizeof(Node));
if(NULL == s)
{
printf(" \r
");
return NULL;
}
s->nDate = Date;
p->pstnext = s;
p = s;
}
else
{
cycle = 0;
}
}
p->pstnext = NULL;
return(head);
}
//
void length(Node *head)
{
Node *p = head->pstnext;
int j=0;
while(NULL != p)
{
p = p->pstnext;
j++;
}
printf("%d\r
", j);
}
//
void research_Date(Node *head, int date)
{
Node *p;
int n=1;
p = head->pstnext;
while(NULL != p && date != p->nDate)
{
p = p->pstnext;
++n;
}
if(NULL == p)
{
printf(" ");
}
else if(date == p->nDate)
{
printf(" %d %d \r
", date, n);
}
return;
}
//
void research_Number(Node *head, int Num)
{
Node *p=head;
int i = 0;
while(NULL != p && i < Num)
{
p = p->pstnext;
i++;
}
if(p == NULL)
{
printf(" \r
");
}
else if(i == 0)
{
printf(" \r
");
}
else if(i == Num)
{
printf(" %d %d\r
", i, p->nDate);
}
}
//
void insert_1(Node *head, int i, int Newdate)
{
Node *pre = head, *New = NULL;
int j = 0;
while(NULL != pre && j < i-1)
{
pre = pre->pstnext;
j++;
}
if(NULL == pre || j > i-1)
{
printf(" \r
");
}
else
{
New = (Node*)malloc(sizeof(Node));
if(NULL == New)
{
printf(" \r
");
return;
}
New->nDate = Newdate;
New->pstnext = pre->pstnext;
pre->pstnext = New;
}
}
//
void insert_2(Node *head, int i, int Newdate)
{
Node *pre = head, *New = NULL;
int j = 0;
while(NULL != pre->pstnext && j < i)
{
pre = pre->pstnext;
j++;
}
if( j == i)
{
New = (Node*)malloc(sizeof(Node));
if(NULL == New)
{
printf(" \r
");
return;
}
New->nDate = Newdate;
New->pstnext = pre->pstnext;
pre->pstnext = New;
}
else
{
printf(" \r
");
}
}
//
void Delete_1(Node *head, int i3)
{
Node *p = head, *pre = NULL;
int j = 0;
while(NULL != p && j < i3)
{
pre = p;
p = p->pstnext;
j++;
}
if(NULL == p)
{
printf(" \r
");
}
else
{
pre->pstnext = p->pstnext;
free(p);
}
}
// ，
int Delete_2(Node *head, int Delete_date)
{
int count = 0;
Node *p = head, *q;
while(NULL != p->pstnext)
{
q = p->pstnext;
if(q->nDate == Delete_date)
{
p->pstnext = q->pstnext;
free(q);
++count;
}
else
{
p = q;
}
}
return count;
}
// ， ，
void Reverse_list(Node *head)
{
Node *q, *s;
if(NULL == head->pstnext || NULL == head->pstnext->pstnext) // head ？
{
return;
}
q = head->pstnext->pstnext;
head->pstnext->pstnext = NULL;
while(NULL != q)
{
s = q->pstnext;
q->pstnext = head->pstnext;
head->pstnext = q;
q = s;
}
}
//
void connect_list(Node *head, Node *head_New)
{
Node *p = head;
while(NULL != p->pstnext)
{
p = p->pstnext;
}
p->pstnext = head_New->pstnext;
}
//
void destroy_list(Node* head)
{
while (NULL != head)
{
Node* temp = head;
head = head->pstnext;
free(temp);
}
}
main()
{
int date, num; //
int i3; //
int i1, i2, Newdate_1, Newdate_2; //
int Delete_date, k; //
Node *Head = NULL; //
Node *Head_New = NULL;
//
Head = creat();
printf(" \r
");
output(Head);
//
printf(" \r
");
length(Head);
//
printf(" \r
");
scanf("%d", &date);
research_Date(Head, date);
//
printf(" \r
");
scanf("%d", &num);
research_Number(Head, num);
// i1 Newdate
printf(" i Newdate");
printf(" i \r
");
scanf("%d,%d", &i1, &Newdate_1);
insert_1(Head, i1, Newdate_1);
printf(" \r
");
output(Head);
// i2 Newdate
printf(" i Newdate");
printf(" i \r
");
scanf("%d,%d", &i2, &Newdate_2);
insert_2(Head, i2, Newdate_2);
printf(" \r
");
output(Head);
// i3
printf(" \r
");
scanf("%d", &i3);
Delete_1(Head, i3);
printf(" \r
");
output(Head);
// ，
printf(" \r
");
scanf("%d", &Delete_date);
k = Delete_2(Head, Delete_date);
printf(" \r
");
output(Head);
printf(" ：");
printf("%d\r
", k);
//
Reverse_list(Head);
printf(" \r
");
output(Head);
//
printf(" \r
");
Head_New = creat();
printf(" ");
output(Head);
printf(" \r
");
connect_list(Head, Head_New);
output(Head);
destroy_list(Head);
} もし、前のいくつかの操作をよく知っていれば、単鎖表逆序はあなたの能力を試すことができます.(実は難しくありません)、肝心なのは構想がはっきりしていることです.まず、単鎖表逆序の原理を見てみましょう.もしあなたが理解を間違えたら、プログラムも書けないかもしれません.原理は図のように示しています.
ここではプログラム中の逆シーケンス関数を解析し,特に,ここの単一チェーンテーブルはheaderを含む単一チェーンテーブルであることを提案した.図を描くのに便利なために、ここではチェーンテーブルに3つしかないと仮定します.1,2,3.より多くの場合は同じです.各文の意味は図で詳細に説明されています.
付1:チェーンヘッダのない単一チェーンテーブル逆シーケンスプログラム
typedef struct student
{
int number;
char name[20];
int score;
struct student *next;
}student;
student *reverse2(student *stu)
{
student *p1,*p2,*p3;
if(stu == NULL ||stu->next == NULL)
return stu;
p1=stu; //p1
p2=p1->next;
p1->next = NULL;
while(p2)
{
p3=p2->next;
p2->next = p1;
p1=p2;
p2=p3;
}
printf("p1 = %d,next = %d
",p1->number,p1->next->number);
stu=p1; // p1
return stu;
}付2:ノーマルシングルチェーンテーブルからノードタイトルを削除する:
ヘッダポインタのない単一チェーンテーブルがあると仮定します.1つのポインタは、この単一チェーンテーブルの中間にあるノード(最初のノードでも最後のノードでもない)を指します.ノードを単一チェーンテーブルから削除してください.
回答:
典型的な「たぬき交換太子」では,このノードを削除するには通常,そのノードの前面ノードのポインタを知るべきであるが,単鎖表にはヘッダノードがないため,そのノードの前面のノードに遡ることができないため,ここでは「移花接木」の手法を採った.このノードをB,次のノードをCとする.では,まずBノードの内容をCノードの内容に置き換え,その後,Cノードを削除することで我々の目的を達成する.コードは次のとおりです.
pcur->next = pnext->next;
pcur->data = pnext->date;
delete pnext;コード#コード#
void DeleteListNode(node* pCurrent)
{
assert(pCurrent != NULL);
node* pNext = pCurrent -> next;
if (pNext == NULL)
pCurrent = NULL;
else
{
pCurrent -> next = pNext -> next;
pCurrent -> data = pNext -> data;
delete pNext;
}
}類似の問題:
1、無頭単鎖表からノードを削除する問題:頭ポインタのない単鎖表があると仮定し、1つのポインタpが単鎖表の1つのノード(最初でも最後でもない)を指している場合、そのノードを削除してください.
2、ヘッドレス単一チェーンテーブルにノードを追加する問題:ヘッドポインタのない単一チェーンテーブルがあると仮定し、1つのポインタpが単一チェーンテーブルの1つのノード(最初でも最後でもない)を指すと仮定し、そのノードの前に新しいノードqを挿入してください.
チェーンテーブルはヘッダレス一方向チェーンテーブルであるため、現在のノードを削除しても、前のノードに新しいノードを挿入しても、pの前のノードを取得する必要があります.ここでは考えを変えて,現在のノードの後続ノードを操作し,前後のノードのデータを適切に交換しても相応の効果が得られる.
問題1解法:p後継ノードp->nextのデータをpにコピーし、p->nextを削除すると、同じ効果が得られます.コードは以下の通りです.
ListNode* p_next = p->next;
p->value=p_next->value;
p->next=p_next->next;
delete p_next;問題2解法:pノードの後にqを追加し,pとqのデータを交換すればよい.
q->next=p->next;
p->next=q;
swap(&p->value, &q->value);拡張の問題:
1つの単一チェーンテーブルを、1回だけ巡回する場合に、単一チェーンテーブルの要素を順番に反転します.
回答:
私の考えはこのようにして、3つのポインタで遍歴して、遍歴の途中で、逆置を行います.