C和指针---第十二章:使用结构和指针
博客专区 > fzyz_sb 的博客 > 博客详情
C和指针---第十二章:使用结构和指针
fzyz_sb 发表于4年前
C和指针---第十二章:使用结构和指针
  • 发表于 4年前
  • 阅读 73
  • 收藏 0
  • 点赞 0
  • 评论 0

【腾讯云】如何购买服务器最划算?>>>   

12.1 链表

链表中的每个节点通过链或指针连接在一起。程序通过指针访问链表中的节点。通常节点是动态分配的,但有时也有节点数组构建的链表,但依旧通过指针来遍历链表的。

12.2 单链表

typedef struct NODE  {
	struct NODE		*link;
	int			value;
}Node;
链表中的节点可能分布于内存中的各个地方。节点在物理上相连与否并不重要,因为程序始终用链(指针)从一个节点移动到另一个节点。

12.2.1 在单链表中插入

#include <stdio.h>
#include <stdlib.h>

typedef struct NODE  {
	struct NODE	*link;
	int		value;
}Node;

int sll_insert( Node **rootp, int new_value )
{
	Node	*current;
	Node	*previous;
	Node	*new;

	current = *rootp;
	previous = NULL;

	while ( current != NULL && current->value < new_value ){
		previous = current;
		current = current->link;
	}

	new = (Node *)malloc( sizeof( Node ) );
	if ( NULL == new ){
		return 0;
	}

	new->value = new_value;
	new->link = current;
	if ( NULL == previous ){
		*rootp = new;
	}
	else{
		previous->link = new;
	}

	return 1;
}

int main(void)
{
	
	//备注:root是指向节点的指针,这样才能不包含任何的数据,而且指向第一个节点
	//如果声明为Node *root,则只是一个节点而已,那么它必须被第一个节点赋值,即本身必须存在值,而不是指向节点的指针了。
	Node	*p1 = (Node *)malloc( sizeof( Node ) );
	Node	*p2 = (Node *)malloc( sizeof( Node ) );
	Node	*p3 = (Node *)malloc( sizeof( Node ) );
	Node	*current;
	p1->value = 5;
	p1->link = p2;

	p2->value = 10;
	p2->link = p3;

	p3->value = 15;
	p3->link = NULL;
	

	sll_insert( &p1, 3 );
	sll_insert( &p1, 12 );
	sll_insert( &p1, 20 );
	current = p1;
	while ( current ){
		printf("%d\n", current->value );
		current = current->link;
	}

	return 0;
}

备注:之前我这里理解出错了,导致写了错误的代码。实际上并不存在指向头节点的指针,即Node**,因为你最终都得初始化为头节点,故直接用头节点的地址传递进去。

函数中第一个参数为Node**,指的意思是头节点的地址,因为这样可以被修改!!!而不是指向头节点的一个额外的指针。

优化单链表的插入:

#include <stdio.h>
#include <stdlib.h>

typedef struct NODE  {
	struct NODE	*link;
	int		value;
}Node;

int sll_insert( register Node **linkp, int new_value )
{
	register Node *current;
	register Node *new;

	while ( ( current = *linkp ) != NULL && current->value < new_value ){
		linkp = &current->link;
	}

	new = (Node *)malloc( sizeof( Node ) );
	if ( NULL == new ){
		return 0;
	}

	new->value = new_value;

	new->link = current;
	*linkp = new;

	return 1;
}

int main(void)
{
 
 //备注:root是指向节点的指针,这样才能不包含任何的数据,而且指向第一个节点
 //如果声明为Node *root,则只是一个节点而已,那么它必须被第一个节点赋值,即本身必须存在值,而不是指向节点的指针了。
 Node	*p1 = (Node *)malloc( sizeof( Node ) );
 Node	*p2 = (Node *)malloc( sizeof( Node ) );
 Node	*p3 = (Node *)malloc( sizeof( Node ) );
 Node	*current;
 p1->value = 5;
 p1->link = p2;


 p2->value = 10;
 p2->link = p3;


 p3->value = 15;
 p3->link = NULL;
 


 sll_insert( &p1, 3 );
 sll_insert( &p1, 12 );
 sll_insert( &p1, 20 );
 current = p1;
 while ( current ){
 printf("%d\n", current->value );
 current = current->link;
 }


 return 0;
}
程序输出:

这种优化是否值得,有待商讨,因为它是函数的调用变得复杂,而且代码增加了阅读的难度。

12.3 双向链表

#include <stdio.h>
#include <stdlib.h>

typedef struct NODE {
	struct NODE		*fwd;
	struct NODE		*bwd;
	int			value;
}Node;

int dll_insert( Node *rootp, int value )
{
	Node *this;
	Node *next;
	Node *newnode;

	for ( this = rootp; ( next = this->fwd) != NULL; this = next ){
		if ( next->value == value ){
			return 0;
		}
		if ( next->value > value ){
			break;
		}
	}

	newnode = (Node *)malloc( sizeof( Node ) );
	if ( newnode == NULL ){
		return -1;
	}
	newnode->value = value;

	if ( next != NULL ){
		if ( this != rootp ){
			newnode->fwd = next;
			this->fwd = newnode;
			newnode->bwd = this;
			next->bwd = newnode;
		}
		else{
			newnode->fwd = next;
			rootp->fwd = newnode;
			newnode->bwd = NULL;
			next->bwd = newnode;
		}
	}
	else{
		if ( this != rootp ){
			newnode->fwd = NULL;
			this->fwd = newnode;
			newnode->bwd = this;
			rootp->bwd = newnode;
		}
		else{
			newnode->fwd = NULL;
			rootp->fwd = newnode;
			newnode->bwd = NULL;
			rootp->bwd = newnode;
		}
	}

	return 1;
}

int main(void)
{
	Node	*rootp = (Node *)malloc( sizeof( Node ) );
	Node	*dp1 = (Node *)malloc( sizeof( Node ) );
	Node	*dp2 = (Node *)malloc( sizeof( Node ) );
	Node	*dp3 = (Node *)malloc( sizeof( Node ) );
	Node	*current;

	dp1->bwd = NULL;		//第一个节点的后向指针为空,而最后一个节点的前向指针为空,根节点指向第一个节点和最后一个节点。
	dp1->fwd = dp2;
	dp1->value = 5;

	dp2->bwd = dp1;
	dp2->fwd = dp3;
	dp2->value = 10;

	dp3->bwd = dp2;
	dp3->fwd = NULL;
	dp3->value = 15;

	rootp->fwd = dp1;
	rootp->bwd = dp3;
	rootp->value = 3;

	dll_insert( rootp, 3 );
	dll_insert( rootp, 12 );
	dll_insert( rootp, 20 );

	current = rootp->fwd;
	while ( current ){
		printf("%d\n", current->value );
		current = current->fwd;
	}

	return 0;
}
程序输出:

但是,我们对代码可以进行简化,简化的代码如下:

int dll_insert( register Node *rootp, int value )
{
	register Node	*this;
	register Node	*next;
	register Node	*newnode;

	for ( this = rootp; ( next = this->fwd) != NULL; this = next ){
		if ( next->value_traits == value ){
			return 0;
		}
		if ( next->value > value ){
			break;
		}
	}
	newnode = (Node *)malloc( sizeof( Node ) );
	if ( NULL == newnode ){
		return -1;
	}
	newnode->value = value;

	newnode->fwd = next;
	this->fwd = newnode;

	if ( this != rootp ){
		newnode->bwd = this;
	}
	else{
		newnode->bwd = NULL;
	}

	if ( NULL != next ){
		next->bwd = newnode;
	}
	else{
		rootp->bwd = newnode;
	}

	return 1;
}
不过,代码的可阅读性的重要性永远高于代码的质量,所以支持第一种写法。

习题:

1. 

#include <stdio.h>
#include <stdlib.h>

typedef struct NODE  {
	struct NODE	*link;
	int		value;
}Node;

int sll_insert( Node **rootp, int new_value )
{
	Node	*current;
	Node	*previous;
	Node	*new;

	current = *rootp;
	previous = NULL;

	while ( current != NULL && current->value < new_value ){
		previous = current;
		current = current->link;
	}

	new = (Node *)malloc( sizeof( Node ) );
	if ( NULL == new ){
		return 0;
	}

	new->value = new_value;
	new->link = current;
	if ( NULL == previous ){
		*rootp = new;
	}
	else{
		previous->link = new;
	}

	return 1;
}

int main(void)
{

	//备注:root是指向节点的指针,这样才能不包含任何的数据,而且指向第一个节点
	//如果声明为Node *root,则只是一个节点而已,那么它必须被第一个节点赋值,即本身必须存在值,而不是指向节点的指针了。
	Node	*p1 = (Node *)malloc( sizeof( Node ) );
	Node	*p2 = (Node *)malloc( sizeof( Node ) );
	Node	*p3 = (Node *)malloc( sizeof( Node ) );
	Node	*current;
	int		count = 0;
	p1->value = 5;
	p1->link = p2;

	p2->value = 10;
	p2->link = p3;

	p3->value = 15;
	p3->link = NULL;


	sll_insert( &p1, 3 );
	sll_insert( &p1, 12 );
	sll_insert( &p1, 20 );
	current = p1;
	while ( current ){
		count++;
		printf("%d\n", current->value );
		current = current->link;
	}

	printf("the code number is: %d\n", count );

	return 0;
}

程序输出:

2. 

#include <stdio.h>
#include <stdlib.h>

typedef struct NODE {
	struct NODE *p_next;
	int	value;
}Node;

int main(void)
{
	Node *p1 = (Node *)malloc( sizeof( Node ) );
	Node *p2 = (Node *)malloc( sizeof( Node ) );
	Node *p3 = (Node *)malloc( sizeof( Node ) );
	Node *p4 = (Node *)malloc( sizeof( Node ) );
	Node *p5 = (Node *)malloc( sizeof( Node ) );
	Node *current;
	int		value = 0;

	p1->p_next = p2;
	p2->p_next = p3;
	p3->p_next = p4;
	p4->p_next = p5;
	p5->p_next = NULL;

	p1->value = 1;
	p2->value = 3;
	p3->value = 5;
	p4->value = 2;
	p5->value = 4;

	current = p1;
	value = 2;
	while ( current ){
		if ( current->value == value ){
			printf("%x---%d", current, current->value );
			break;
		}
		current = current->p_next;
	}
	if ( NULL == current){
		printf("not found\n");
	}

	return 0;
}

并没有封装成函数。程序输出:

3.

#include <stdio.h>
#include <stdlib.h>

typedef struct NODE {
	struct NODE		*fwd;
	struct NODE		*bwd;
	int			value;
}Node;

int dll_insert( Node *head, Node *tail, int value )
{
	Node *this;
	Node *next;
	Node *newnode;

	for ( this = head; ( next = this->fwd ) != tail; this = next ){
		if ( next->value == value ){
			return 0;
		}
		if ( next->value > value ){
			break;
		}
	}

	newnode = (Node *)malloc( sizeof( Node ) );
	if ( NULL == newnode ){
		return -1;
	}
	newnode->value = value;

	if ( tail != next ){
		if ( this != head ){
			newnode->fwd = next;
			this->fwd = newnode;
			newnode->bwd = this;
			next->bwd = newnode;
		}
		else{
			newnode->fwd = next;
			head->fwd = newnode;
			newnode->bwd = head;
			next->bwd = newnode;
		}
	}
	else{
		if ( this != head ){
			newnode->fwd = tail;
			this->fwd = newnode;
			newnode->bwd = this;
			tail->bwd = newnode;
		}
		else{
			newnode->fwd = tail;
			head->fwd = newnode;
			newnode->bwd = head;
			tail->bwd = newnode;
		}
	}
}

int main(void)
{
	Node	*head = (Node *)malloc( sizeof( Node ) );
	Node	*tail = (Node *)malloc( sizeof( Node ) );
	Node	*dp1 = (Node *)malloc( sizeof( Node ) );
	Node	*dp2 = (Node *)malloc( sizeof( Node ) );
	Node	*dp3 = (Node *)malloc( sizeof( Node ) );
	Node	*current;

	dp1->bwd = head;		//第一个节点的后向指针为空,而最后一个节点的前向指针为空,根节点指向第一个节点和最后一个节点。
	dp1->fwd = dp2;
	dp1->value = 5;

	dp2->bwd = dp1;
	dp2->fwd = dp3;
	dp2->value = 10;

	dp3->bwd = dp2;
	dp3->fwd = tail;
	dp3->value = 15;

	head->fwd = dp1;
	tail->bwd = dp3;

	dll_insert( head, tail, 3 );
	dll_insert( head, tail, 12 );
	dll_insert( head, tail, 20 );

	current = head->fwd;
	while ( current != tail ){
		printf("%d\n", current->value );
		current = current->fwd;
	}

	return 0;
}

备注:虽然代码量多了点,但是个人感觉阅读起来更轻松吧。程序输出:

4. 这道题的答案从Google上搜来的,最后发现其实自己想的和答案的意义,但是唯一的区别是:我用到的是指针,导致赋值的时候进行了覆盖。而原答案没用到指针,可以临时建立节点。代码如下:

#include <stdio.h>

typedef struct Node {
	char	value;
	struct	Node	*next; 
} Node;

void print_list( Node *root )
{
	while ( root ){
		printf("%c-->", root->value );
		root = root->next;
	}
	printf("NULL\n");
}

void reverse_list( Node *root )
{
	Node *new_root = 0;
	while ( root ){
		Node *next = root->next;
		root->next = new_root;
		new_root = root;
		root = next;
	}
}

int main(void)
{
	Node d = { 'd', 0 };
	Node c = { 'c', &d };
	Node b = { 'b', &c };
	Node a = { 'a', &b };

	print_list( &a );
	reverse_list( &a );
	print_list( &d );

	return 0;
}
程序输出:

5. 

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
	char	value;
	struct	Node	*next; 
} Node;

void print_list( Node *root )
{
	while ( root ){
		printf("%c-->", root->value );
		root = root->next;
	}
	printf("NULL\n");
}

int sll_remove( Node **rootp, Node *node )
{
	Node *current = *rootp;
	Node *previous = NULL;
	while ( current ){
		if ( current == node ){
			current = current->next;
			if ( previous ){
				previous->next = current;
			}
			else{
				( *rootp ) = ( *rootp )->next;	//头节点进行特殊处理
			}
			return 1;
		}
		previous = current;
		current = current->next;
	}

	return 0;
}

int main(void)
{
	Node *a = (Node *)malloc( sizeof( Node ) );
	Node *b = (Node *)malloc( sizeof( Node ) );
	Node *c = (Node *)malloc( sizeof( Node ) );
	Node *d = (Node *)malloc( sizeof( Node ) );
	Node *falseNode = (Node *)malloc( sizeof( Node ) );

	a->next = b;
	b->next = c;
	c->next = d;
	d->next = NULL;
	a->value = 'a';
	b->value = 'b';
	c->value = 'c';
	d->value = 'd';

	falseNode->next = d;
	falseNode->value = 'dd';

	print_list( a );
	sll_remove( &a, a );	//删除头节点
	print_list( a );

	sll_remove( &a, c );	//删除中间节点
	print_list( a );

	sll_remove( &a, falseNode );	//删除一个错误的节点
	print_list( a );

	return 0;
}

程序输出:

使用节点而不是一个值的好处是:你可以直接进行节点的比较和赋值。

6.

#include <stdio.h>
#include <stdlib.h>

typedef struct NODE {
	struct NODE		*fwd;
	struct NODE		*bwd;
	char			value;
} Node;

void print_list( struct NODE *rootp ){
	Node *current = rootp->fwd;
	while ( current ){
		printf("%c-->", current->value );
		current = current->fwd;
	}
	printf("NULL\n");
}

int dll_remove( struct NODE *rootp, struct NODE *node )
{
	Node *current = rootp->fwd;
	Node *previous = NULL;

	while ( current ){
		if ( current == node ){
			if ( previous ){				//解决头节点为删除的节点的特殊情况
				previous->fwd = current->fwd;
			}
			else{
				rootp->fwd = current->fwd;
			}
			if ( current->fwd ){	
				current->fwd->bwd = previous;
			}
			else{
				rootp->bwd = previous;		//解决尾节点为删除节点的特殊情况
			}
			return 1;
		}
		previous = current;
		current = current->fwd;
	}

	return 0;
}

int main(void)
{
	Node	*rootp = (Node *)malloc( sizeof( Node ) );
	Node	*dp1 = (Node *)malloc( sizeof( Node ) );
	Node	*dp2 = (Node *)malloc( sizeof( Node ) );
	Node	*dp3 = (Node *)malloc( sizeof( Node ) );
	Node	*dp4 = (Node *)malloc( sizeof( Node ) );
	Node	*dp5 = (Node *)malloc( sizeof( Node ) );
	Node	*dp6 = (Node *)malloc( sizeof( Node ) );

	dp1->bwd = NULL;		//第一个节点的后向指针为空,而最后一个节点的前向指针为空,根节点指向第一个节点和最后一个节点。
	dp1->fwd = dp2;
	dp1->value = 'a';

	dp2->bwd = dp1;
	dp2->fwd = dp3;
	dp2->value = 'b';

	dp3->bwd = dp2;
	dp3->fwd = dp4;
	dp3->value = 'c';

	dp4->bwd = dp3;
	dp4->fwd = dp5;
	dp4->value = 'd';

	dp5->bwd = dp4;
	dp5->fwd = dp6;
	dp5->value = 'e';

	dp6->bwd = dp5;
	dp6->fwd = NULL;
	dp6->value = 'f';

	rootp->fwd = dp1;
	rootp->bwd = dp6;

	print_list( rootp );

	dll_remove( rootp, dp1 );
	print_list( rootp );

	dll_remove( rootp, dp6 );
	print_list( rootp );

	dll_remove( rootp, dp4 );
	print_list( rootp );

	return 0;
}

程序输出:

7.

#include <stdio.h>
#include <stdlib.h>

//保存由value开头的所有单词
typedef struct SWORD{
	struct SWORD	*next;
	char		*value;
} Sword;

//一个链表,保存所有的单词
typedef struct NODE{
	struct NODE	*next;
	struct SWORD	*value;
} Node;

//打印整个链表
void print_list( Node *node )
{
	Node *current = node;
	while ( current ){
		Sword *currentWord = current->value;
		while ( currentWord ){
			printf("%s-->", currentWord->value );
			currentWord = currentWord->next;
		}
		printf("NULL\n");
		current = current->next;
	}
}

//在表SWORD中查找是否出现单词string
int sll_find( Sword *sword, char *string )
{
	Sword *current = sword;
	while ( current ){
		if ( current->value == string ){
			return 1;
		}
		current = current->next;
	}

	return 0;
}

//在单词表中插入单词string
void sll_insertWord( Sword **sword, char *string )		//传入的指针必须为指向头节点的指针,否则当节点为空的时候,无法完成插入
{
	Sword *current = *sword;
	Sword *previous = NULL;
	Sword *new;
	while ( current != NULL && current->value < string ){
		previous = current;
		current = current->next;
	}
	
	new = (Sword *)malloc( sizeof( Sword ) );
	if ( NULL == new ){
		return;
	}
	new->value = string;

	new->next = current;
	if ( previous ){
		previous->next = new;
	}
	else{
		*sword = new;			//处理链表为空的情况
	}
}

void sll_insertWordList( Node **node, Sword *sword )		
{
	Node *current = *node;
	Node *previous = NULL;
	Node *new;
	while ( current != NULL && current->value < sword ){
		previous = current;
		current = current->next;
	}

	new = (Node *)malloc( sizeof( Node ) );
	if ( NULL == new ){
		return;
	}
	new->value = sword;

	new->next = current;
	if ( previous ){
		previous->next = new;
	}
	else{
		*node = new;
	}
}

int sll_insertNode( Node **node, char *string )
{
	char	ch = *string;
	Node	*current = *node;
	Node	*previous = NULL;
	Sword	*newword;
	while ( current != NULL ){
		if ( ch == *(current->value->value) ){				//存在包含和string一样开头字母的单词
			if ( sll_find( current->value, string ) ){
				return 0;
			}
			else{
				sll_insertWord(&current->value, string );
				return 1;
			}
		}
		previous = current;								//用于判断node是否为空的链表
		current = current->next;
	}

	newword = (Sword *)malloc( sizeof( Sword ) );
	if ( NULL == newword ){
		return 0;
	}
	newword->next = NULL;
	newword->value = string;
	sll_insertWordList(&current, newword );
	if ( previous ){
		previous->next = current;					//如果链表不为空,则将节点插入到链表中
	}
	else{
		( *node )->next = NULL;						//如果链表为空,则进行特殊处理
		( *node )->value = newword;
	}

	return 0;
}

int main(void)
{
	char a[] = "aaa";
	char b[] = "aab";
	char c[] = "ccc";
	char d[] = "ddd";
	char e[] = "ddf";

	Sword *sword = (Sword *)malloc( sizeof( Sword ) );
	Node *node = (Node *)malloc( sizeof( Node ) );

	sword->next = NULL;
	sword->value = a;

	
	node->next = NULL;
	node->value = sword;

	sll_insertNode( &node, b );
	sll_insertNode( &node, c );
	sll_insertNode( &node, d );
	sll_insertNode( &node, e );
	print_list( node );

	return 0;
}

程序输出:

备注:做出这道题,心情突然好愉快。

标签: C和指针
共有 人打赏支持
粉丝 370
博文 209
码字总数 447144
×
fzyz_sb
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: