C语言实现两数相加2018

时间:2019-09-23 12:07来源: 操作系统
/*给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。 includeiostream using namespace std; //单链表 typedef struct

/*给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

include<iostream>

using namespace std;

//单链表

typedef struct Lnode{

int data;

struct Lnode *next;

}Lnode;

//双链表

typedef struct DLnode{

int data;

struct DLnode *next;

}DLnode;

/*

尾插法建立单链表

*/

Lnode * Create(Lnode *head, int *a, int n){

Lnode *first, *node;

first = (Lnode *)malloc(sizeof(Lnode)); //头结点

head = first;

first->next = NULL;

for (int i = 0; i < n; ++i){

node = (Lnode *)malloc(sizeof(Lnode));

node->data = *(a + i);

first->next = node;

first = first->next;

}

first->next = NULL;

return head;

}

/*

头插法建立单链表

*/

Lnode * HeadCreate(Lnode *head, int *a, int n){

Lnode *first, *node;

first = (Lnode *)malloc(sizeof(Lnode)); //头结点

head = first;

first->next = NULL;

for (int i = 0; i < n; ++i){

node = (Lnode *)malloc(sizeof(Lnode));

node->data = *(a + i);

node->next = first->next;

first->next = node;

}

return head;

}

/*

在指定位置插入节点val

*/

Lnode * Insert(Lnode * head, int n, int val){

Lnode *p = head;

Lnode node = (Lnode)malloc(sizeof(Lnode));

for (int i = 0; i < n - 1; ++i){

p = p->next;

}

node->data = val;

node->next = p->next;

p->next = node;

return head;

}

/*

删除 data 为val的某个节点

*/

int Del(Lnode *head, int val){

Lnode*p, *q;

p = head; //传入头指针,然后p保存头指针信息,修改p,即等同于修改head头指针

while (p->next != NULL){ //p指向删除节点的前一个节点

if (p->next->data == val)

{

break;

}

p = p->next;

}

if (p->next == NULL){

return 0;

}

else{

q = p->next;

p->next = q->next;

free(q);

return 1;

}

}

/*

单链表反转

*/

Lnode* Reverse(Lnode *head){

Lnode *first = head->next, *tmp;

head->next = NULL;

while (first != NULL)

{

tmp = first->next;

first->next = head->next;

head->next = first;

first = tmp;

}

return head;

}

/*

  • 构建有环单链表

*/

Lnode *CirLnode(Lnode *head, int num) {

Lnode *tmp, *tail;

tmp = tail = head->next;

for (int i = 1; i < num; ++i) {

tmp = tmp->next;

}

while (tail->next != NULL) {

tail = tail->next;

}

tail->next = tmp;

return head;

}

/*

  • 判断单链表是否有环

*/

int IsCir(Lnode *head) {

Lnode *first, *last;

first = head;

last = head;

while (last != NULL && last->next != NULL) {

last = last->next->next;

first = first->next;

if (first == last) {

cout << first->data << endl; //在环中相遇的点,不一定是环的初始点

//求环的初始点

first = head;

while (first->next!=NULL){ //first和last在环中相遇的时候,使first指针回到head节点,last不动,然后first和last都每次走一步,两者再次相遇的点就是环的初始节点

first = first->next;

last = last->next;

if (first == last){

cout << "初始环点" << first->data << endl;

break;

}

}

return 1;

}

}

return 0;

}

/*

约瑟夫环问题

*/

int JoseCircle(Lnode *head,int num){

Lnode p = head,tmp,*q;

int i = 1;

q = p->next;

while (p!=q){

i++;

p = q;

q = q->next;

if (i == num){

tmp = q;

p->next = tmp->next;

q = p->next;

free(tmp);

i = 1;

}

}

return q->data;

}

/*

查找单链表中的倒数第K个结点(k > 0)

*/

int FindLast(Lnode * head, int k){

Lnode *p, *q;

q = head;

p = q->next;

for (int i = 0; i < k; ++i){ //使用两个指针,前面的指针走到正K,后面的指向第一个,两者相差为k-1,然后同时走,直到前面走到最后,后指针的位置即为所求

q = q->next;

}

if (q == NULL){ //k大于链表个数

return -1;

}

while (q->next != NULL){

p = p->next;

q = q->next;

}

/*

while(p){

p=p->next;

i++;

if(i>k) q=q->next; //p先走,只有存在p走过了K个节点,q才开始走,当p走到终点,q指向倒数K个节点

}

if(q==head) return 0; //q要么指向头结点,要么指向倒数第K个

else cout<<q->data<<endl;

*/

return p->data;

}

/*

  • 删除相同节点

*/

Lnode *DelSame(Lnode *head) {

Lnode *p, *q, *tmp;

p = head->next;

while (p != NULL) {

q = p;

while (q->next != NULL) {

if (q->next->data == p->data) {

tmp = q->next;

q->next = tmp->next;

free(tmp);

}

else{

q = q->next;

}

}

p = p->next;

}

return head;

}

/*

查找单链表的中间节点

*/

int FindMid(Lnode *head){

Lnode *p, *q;

p = q = head->next;

while (q->next != NULL){

if (q->next->next != NULL){

p = p->next;

q = q->next->next;

}

else{

break;

}

}

return p->data;

}

/*

统计节点的个数

*/

int CalcNum(Lnode *head){

int n = 0;

Lnode *tmp = head;

if (head->next == NULL){

return n;

}

else{

while (tmp->next != NULL){

n++;

tmp = tmp->next;

}

return n;

}

}

/*

  • 合并两个有序链表

*/

Lnode *MergeLnode(Lnode *h1, Lnode *h2) {

Lnode *p1, *p2, *p3, *q;

p1 = h1->next, p2 = h2->next;

q = p3 = h1;

q->next = NULL;

while (p1 != NULL && p2 != NULL) {

if (p1->data <= p2->data) {

q->next = p1;

p1 = p1->next;

}

else {

q->next = p2;

p2 = p2->next;

}

q = q->next;

}

if (p1 != NULL) q->next = p1;

if (p2 != NULL) q->next = p2;

return p3;

}

/*

  • 求A,B链表的差集A-B

*/

Lnode *Diff(Lnode *h1, Lnode *h2) {

Lnode *p = h1, *q = h2;

Lnode *tmp;

while (p->next != NULL && q->next != NULL) {

if (p->next->data < q->next->data) {

p = p->next;

}

else if (p->next->data > q->next->data) {

q = q->next;

}

else {

tmp = p->next;

p->next = tmp->next;

free(tmp);

}

}

return h1;

}

/*

求A,B链表的交集

*/

void Common(Lnode *h1, Lnode *h2){

Lnode *p = h1, *q = h2;

while (p->next != NULL && q->next != NULL) {

if (p->next->data < q->next->data) {

p = p->next;

}

else if (p->next->data > q->next->data) {

q = q->next;

}

else {

cout << p->next->data << " ";

p = p->next;

q = q->next;

}

}

cout << endl;

}

/*

删除单链表中的最小值节点

*/

Lnode *DelMin(Lnode *head){

Lnode *q = head->next, min = q,tmp=head;

while (q != NULL && q->next!=NULL){

if (q->next->data < min->data){

tmp = q;

min = q->next;

}

q = q->next;

}

tmp->next = min->next;

free(min);

return head;

}

/*

将A链表拆分成A,B,其中A是data为奇数的点,B是data为偶数的点,顺序不变

*/

Lnode * SplitLink(Lnode *h1, Lnode *h2){

Lnode p = h1,t ;

Lnode *q = (Lnode *)malloc(sizeof(Lnode));

h2 = q;

q->next = NULL;

while (p->next != NULL){

if (p->next->data % 2 == 0){ //如果是偶数,就取出 放到B中,否则就继续前进,然后A就剩余奇数

t = p->next;

p->next = t->next;

t->next = NULL;

q->next = t;

q = q->next;

}

else{

p = p->next;

}

}

return h2;

}

/*

按照val值将单链表分成左右部分,左边比它小,右边比它大

*/

Lnode * Partation(Lnode *head,int val){

Lnode *p = head;

Lnode *small, *equal, *big; //将单链表拆成三个链表, 分别定义三个头指针,

small = equal = big = NULL;

Lnode * smallA, *equalA, *bigA ; //三个链表的尾指针

smallA = equalA = bigA = NULL;

while (p->next!=NULL){

if (p->next->data < val){

if (small == NULL){ //初始时,头尾指针均指向第一个进入大,等,小的节点

smallA = small = p->next;

}

else{

smallA->next = p->next; //不是第一个节点的时候,采用尾插法将节点插入链表

smallA = smallA->next;

}

}

else if (p->next->data == val){

if (equal == NULL){

equalA = equal = p->next;

}

else{

equalA->next = p->next;

equalA = equalA->next;

}

}

else {

if (big == NULL){

bigA = big = p->next;

}

else{

bigA->next = p->next;

bigA = bigA->next;

}

}

p = p->next;

}

if (small!=NULL && equalA != NULL) { //当小链表不为空,且等链表不为空,链接两个链表,等链表后置为空

equalA->next = NULL;

smallA->next = equal;

}

if (equalA!=NULL && bigA != NULL) { // 同理链接等链表和大链表

bigA->next = NULL;

equalA->next = big;

}

head->next = small != NULL ? small : equal != NULL ? equal : big;

return head;

}

/*

正序打印单链表

*/

void show(Lnode * head){

while (head->next != NULL){

cout << head->next->data << " ";

head = head->next;

}

cout << endl;

}

/*

逆序打印单链表

*/

void ShowTail(Lnode *head) { //print from tail,颠倒顺序的问题,采用栈,并且去掉头结点

Lnode *p = head;

if (p == NULL) {

return;

}

ShowTail(p->next);

cout << p->data << " ";

}

void tt(int *p){

int a = 3;

int *q = p;

q = &a;

}

void test(Lnode *head){ //一个单链表,first指针在前,last指针在后,first置空后,last便访问不到first后的节点

//last置空后,并不妨碍first访问后面的节点

Lnode *p = head->next;

Lnode *q = p;

p = p->next->next;

p->next = NULL;

q = q->next;

cout << p->data << endl;

}

void main(){

int a[] = {2,1,3,5,4};

int b[] = { 3,4, 5, 6, 7, 8 };

int lenA = sizeof(a) / sizeof(a[0]);

int lenB = sizeof(b) / sizeof(b[0]);

Lnode *head = NULL, *tail = NULL , *h2=NULL; //头指针

head = Create(head, a, lenA); //指针作为函数参数时,传递的也是指针的地址拷贝,所以指正不会改变,传入堆指针时,指针的值才会变化

show(head);

tail = HeadCreate(tail, b, lenB);

Reverse(tail);

show(tail);

/*

cout << "节点个数为: " << CalcNum(head) << endl;

*tail = Reverse(tail);

show(tail);

if (Del(head, 4) > 0){

cout << "找到并删除" << endl;

show(head);

}

Insert(head, 3, 6);

show(head);

cout << "节点个数为: " << CalcNum(head) << endl;

cout << FindMid(head) << endl;

head = DelMin(head);

show(head);

h2=SplitLink(head, h2);

show(head);

show(h2);

int *p = (int *)malloc(sizeof(int));

tt(p);

if (p == NULL){

cout << "null" << endl;

}

else{

cout << " not null" << endl;

}

*/

//head = CirLnode(head, 1);

/*if (IsCir(head)){

cout << "has a circle " << endl;

}

else{

cout << "no circle " << endl;

}*/

//cout << "Last out " << JoseCircle(head, 3) << endl;

//Common(head, tail);

head = Partation(head, 2);

show(head);

free(head);

free(tail);

system("pause");

}

你可以假设除了数字 0 之外,这两个数字都不会以零开头。

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807*/
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
struct ListNode *p = NULL, *q = NULL, *head = NULL;

int index = 0, x, y, sum = 0;

while (l1 != NULL || l2 != NULL)
{
x = (l1 != NULL) ? l1->val : 0;/*当l1非空时x等于l1所指向的值*/
y = (l2 != NULL) ? l2->val : 0;/*当l2非空时y等于l2所指向的值*/

sum = x + y + index;/*求和的时候记得加上用来进位的index*/

p = (struct ListNode*)malloc(sizeof(struct ListNode));
if (p != NULL)/*当节点分配成功*/
{
p->val = sum % 10;/*对和求余数*/
index = sum / 10;/*计算是否需要进位*/
p->next = NULL;
}
if (q == NULL)/*才产生了一个节点的时候,让head指向该节点*/
{
q = p;
head = q;
}
else
{
q->next = p;/*将每一个节点连接起来*/
q = p;
}
/*判断l1是否已经指向了一个空节点,这一步很重要, 也很危险,切记不能写成if(l1->next!NULL)这样会产生死循环(l1和l2一直指向最后一个节点)*/
if
l1 = l1->next;
if
l2 = l2->next;
}
if (index == 1)/*当最后一个节点相加超过10了,需要再产生一个节点来完成进位*/
{
p = (struct ListNode*)malloc(sizeof(struct ListNode));
if (p != NULL)
{
p->val = 1;
p->next = NULL;
q->next = p;
q = p;
}

}
return head;
}
/*心得:

*1、写过程略微复杂一点的程序一定要写好伪代码,然后在写的过程中再转化为标准C语言;

*2、对于指针的使用,在指针改变指向,即移动或者交换的时候一定要留心,当指针移动的时候出现麻烦,可以往后思考一步到两步,就可以发现其问题;

*3、对于相似问题的求解,一定要学会归纳一个模型,即使用几行代码就可以实现一系列相似问题的求解。

*/

编辑: 操作系统 本文来源:C语言实现两数相加2018

关键词:

  • 上一篇:没有了
  • 下一篇:没有了