struct node
{
int val;
node* next;
};
//此处需要注意,如果写成void create(node* head,int n)
//这样即使创建了链表,也没有作用,因为node* head是形参
//在函数内部是对这个指针的拷贝进行操作,故不传回链表
//正确形式应该是void create(node* &head,int n)
node* create(unsigned int n)
{
node *head = new node;
node *p = head, *q;
head->val = rand() % RAND_MAX;
cout << "创建节点:" << 0 << " 值:" << head->val << endl;
for (size_t i = 1; i < n; i++)
{
q = new node;
q->val = rand() % RAND_MAX;
cout << "创建节点:" << i << " 值:" << q->val << endl;
p->next = q; //链表叠加
p = p->next;
}
p->next = NULL; //切记尾端处理
return head;
}
void erase(node* head)
{
if (NULL == head) return;
node *tmp;
while (head)
{
tmp = head;
head = head->next;
delete tmp;
}
}
int getnodelen(node* head)
{
int n = 0;
node *temp=head;
while (temp)
{
n++;
temp = temp->next;
}
return n;
}
//此题原本做法出现两处错误
//(1)void delnode(node* head, int num),此处head传递进入的是指针的拷贝,如果头节点被改变,就呵呵了
//(2)逻辑错误,原程序中只若是头节点相等,删除操作后就返回了,这种考虑是不完全的
void delnode(node* &head, int num)
{
if (NULL == head) return;
node *temp, *p = head;
//删除从头节点连续相等数值
while (head != NULL&&head->val == num)
{
temp = head;
head = head->next;
delete temp;
cout << "删除头节点,数值为:" << num << endl;
}
if (head) p = head;
else return;
while (p->next)
{
if (p->next->val == num)
{
temp = p->next;
//错误写成p = temp->next;
p->next = temp->next;
delete temp;
cout << "删除节点,数值为:" << num << endl;
}
else
{
p = p->next;
}
}
}
//在链表中第i个位置插入节点,即在第i个节点前插入元素
bool insert_n_list(node* &head, int n, int num)
{
if (n < 1 || head == NULL) return false;
int i = 1;
node *temp, *p = head;
//插入头节点
if (n == 1)
{
temp = new node;
temp->val = num;
temp->next = head;
head = temp;
return true;
}
while (p != NULL&&i < n - 1)
{
++i;
p = p->next;
}
if (i == n - 1 && p != NULL) //寻找到插入节点
{
temp = new node;
temp->val = num;
temp->next = p->next;
p->next = temp;
return true;
}
else
{
return false;
}
}
void printnodelist(node* head)
{
if (NULL == head) return;
node *temp = head;
while (temp)
{
cout << " " << temp->val << "," ;
temp = temp->next;
}
cout << endl;
}
//按升序排列(仅进行值交换,不进行指针交换)
void sort_nodelist(node* head)
{
if (head == NULL || head->next == NULL)
return;
node *p = head;
bool sign = false;
int i, j, len = getnodelen(head), temp;
for (i = len - 1; i > 0; i--)
{
sign = false;
p = head;
for ( j = 0; j < i; j++)
{
if (p->val>p->next->val)
{
sign = true;
temp = p->val;
p->val = p->next->val;
p->next->val = temp;
}
p = p->next;
}
if (!sign)
break; //此趟排序未发生交换
}
}
void reverse_nodelist(node* &head)
{
//空链表或者单节点链表不进行转置
if (head == NULL || head->next == NULL)
return;
node *p1 = head, *p2 = head->next, *p3;
while (p2)
{
p3 = p2->next;
p2->next = p1;
p1 = p2;
p2 = p3;
}
//此处需注意最后一个节点是NULL,只有当P2为NULL时,转置方才完成
//此时将NULL,即P2后面的P1提取出来作为头节点,转置完成
head->next = NULL;
head = p1;
}
2015年8月5号添加:
//可以调用递归做,但是如果链表较长,易导致栈溢出
void print_reverse(node* list)
{
if (NULL == list)
return;
//单节点单独处理
if (NULL == list->next)
{
cout << " " << list->val << endl;
return;
}
node* temp;
stack<int> print;
while (NULL != temp)
{
print.push(temp->val);
temp = temp->next;
}
int val;
while (!print.empty()) //stack若为空,用empty判断返回true
{
val = print.top();
cout << " " << val << ",";
print.pop();
}
cout << endl;
}
转载于:https://www.cnblogs.com/jason1990/p/4702422.html